sgc109   1년 전

일단 저는 이 문제를 약간은 수학적인 규칙을 이용하여 풀었는데 이문제를 다른 방법으로 푸신 분이 계시다면

다른 풀이를 알고싶습니다. 왜냐하면 뭔가 다른 더 깔끔하고 직관적인 방법이 있을것같은데 아무리 생각해도 떠오르지가 않았

기때문입니다.


우선 제 풀이방식을 말씀드리자면

우선 최소장치작동 횟수가 같은 거리중 최대값을 가지는 거리를 구하였습니다.

한번 장치를 작동시킬때 움직이는 거리를 순서대로 적어볼때

1

11

121

1221

12321

123321

1234321

과 같이 좌우 대칭일때의 거리에서 1이 증가하면 장치작동횟수가 1이 증가하는 것을 발견했습니다.


그래서 좌우대칭일때의 거리를 차례대로써보니

1 2 4 6 9 12 16 20

이었고 이 수들의 규칙을 찾아보니, 증가량이 1 2 2 3 3 4 4 ... 라는 것을 이용하여

두행성사이의 거리가 ( n^2 , n^2 + n ] 구간에 있으면 최소 장치작동횟수는 2n 번이고

(n^2 + n , n^2 + 2n + 1] 구간에 있으면 최소 장치작동횟수가 2n+1 번이라는결과를 도출해내어


반복문으로 거리가 1부터 구간에 걸릴때까지 무한반복으로 해놓고

거리가 1일땐 바로 1을 출력하게했고 2이상일땐 위에 써놓은 구간에 걸릴때 장치작동횟수를 출력하고 break 하도록

해서 문제를 풀수가 있었습니다.


이 방법외에 어떤 풀이가 있을까요?? 궁금합니다..

댓글을 작성하려면 로그인해야 합니다.