백준 1011번 Fly me to the Alpha Centauri

www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri

 1칸 - 1 /1

2칸 - 11 /2

3칸 - 111 /3
    4칸 - 1 2 1 /3

5칸 - 1 2 1 1 /4
6칸 - 1 2 2 1 /4

7칸 - 1 2 2 1 1 /5
8칸 - 1 2 2 2 1 /5
    9칸 - 1 2 3 2 1 /5  3

10칸 - 123211 /6 3.1622
11칸 - 123221 /6  3.3166
12칸 - 123321 /6  3.4641

13칸 - 1233211/7  3.6
14칸 - 1233221 /7
15칸 - 1233321 /7
    16칸 - 1234321 / 7

규칙 찾기가 힘들었는데 결론은

제곱근을 활용한 해법이 있었다. 

 

1. 제곱근 == 정수 : 횟수=제곱근 * 2 - 1

2. 제곱근 반올림(소숫점이 .5 이상)해서 올림 : 횟수 = 제곱근 * 2 + 1

3. 제곱근 반올림 해서 내림 : 횟수 = 제곱근 * 2