열무의 코딩일기

접근법 문제를 단순화하는게 생각보다 어려웠다. 그러나 목적은 조건에 맞도록 가장 최소한의 장치를 작동시키면 된다. 따라서 주어진 조건을 만족시키는 수열을 하나씩 만들어봤다. ( 아래 그림 참조! ) 어차피 입력값으로 받는 시작점과 끝점 사이의 거리 (Distance) 가 핵심이기 때문에 이 거리 값에 맞게 답을 구하면 된다. 하나씩 나열해보면, 찾을 수 있는 규칙이 있다. 제곱수 시점에서 횟수가 1 증가한다. 제곱수를 N이라고 한다면, N에서 양의 제곱근 (이하 n) 을 뺀 시점에서 또 횟수가 증가한다. 여기서, N(제곱수)의 바로 전 시점까지의 횟수는 2n - 1 N - n 의 직전 시점에서의 횟수는 2n - 2 Distance 의 값을 알고 있다면 위 규칙을 따라서 손쉽게 문제를 풀 수 있다. Dis..