Backjoon 1010번 다리놓기

1010번 다리 놓기

https://www.acmicpc.net/problem/1010

1010번: 다리 놓기

 

 

---

정답 코드

 

---

문제 설명입니다.

 

간단한 경우의 수 문제입니다.

이번문제의 풀이법을 찾는데 그렇게 오랜 시간이 걸리지 않습니다. 아래 수식을 이용하면 간단 합니ㅏㄷ.

일단 입력 조건입니다.

첫줄에 테스트 개수를 받고 그 다음부터 테스트 입력을 받습니다.

 

위에 조건중에 가장 중요한 조건은 왼쪽의 숫자가 오른쪽의 숫자보다 항상 작습니다.

강서쪽의 점의 개수가 강 동쪽의 점의 개수보다 언제나 작습니다.

시간 복잡도는 2n^2 정도 인것 같습니다. 

---

인터넷을 찾아 보시면 시간 복잡도를 줄이는 방법이 많이 있습니다. 하지만 이 문제는 이정도만 해도 간단하게 풀립니다.

깃헙에서 시간 복잡도 n으로 푸신 분이 있어 공유 드립니다.

• https://kminito.github.io/baekjoon/2018/05/15/baekjoon_1010.html

 

---

 

사실 이번 문제는 정답률이 47%로 높은 정답률이면서 문제 난이도를 생각하면 낮은 정답률이기도 합니다.
복잡한 수학공식, 알고리즘이 적용되는 문제들이 많지만 가끔 이렇게 주먹구구식으로 풀어도 쉽게 풀리는 문제들이 많습니다.

문제를 풀때 키보드 보다 펜에 먼저 손이 가는 습관이 좋은 습관인 것 같습니다.