[백준] 1011번 문제 (Fly me to the Alpha Centauri) 파이썬(Python) 풀이

문제 내용

규칙을 찾으려고 반나절동안 노력 했으나 결국 찾지 못했고 다른 사람의 정답을 찾아보게 되었다..

 

공간이동량이 포물선 형태로 만들어져서 거리의 절반 정도에서 -1 씩 해가며 카운트를 시도했으나 당연히 그 규칙이 아니기 때문에 매몰차게 틀려버렸다.

 

결국 이 문제를 풀기 위해서는 경우의 수를 어느정도 노트에 쭉 적어보며 적힌 내용을 보고 규칙을 찾는게 우선이었다.

 

그 경우의 수의 표는 다음과 같다..

 

거리	이동	이동 횟수
1	1	1
2	11	2
3	111	3
4	121	3
5	1211	4
6	1221	4
7	12211	5
8	12221	5
9	12321	5
10	123211	6
11	123221	6
12	123321	6
13	1233211	7
14	1233221	7
15	1233321	7
16	1234321	7

우선 밑줄친 숫자들을 보면 제곱수다.

4는 2의 제곱

9는 3의 제곱

16은 4의 제곱 

 

제곱 수일 경우에는 제곱근 * 2 - 1이 최소 카운트가 된다 

4의 경우 2 * 2 - 1 = 3

9의 경우 3 * 2 - 1 = 5

16의 경우 4 * 2  - 1 = 7

 

그럼 나머지는 어떻게 구할까..

 

import math

for tc in range(int(input())):
    x, y = map(int, input().split())
    dist = y - x  # 실 이동 거리
    sq = int(math.sqrt(dist))  # 제곱근
    etc = dist - sq ** 2  # 나머지
    count = sq * 2 - 1
    if etc == 0:
        print(count)
    elif etc <= sq:
        print(count + 1)
    else:
        print(count + 2)

 

결론만 말하면 제곱근이 나머지 보다 크거나 같으면 카운트 +1을 해줘 출력한다.

 

5를 예로 들면 

5의 제곱근은 2.xxx이지만 int()를 써줘서 2가 된다.

다음으로는

(거리) - (제곱근의 제곱)을 해준다 

= 5 - 2 ^ 2

그럼 나머지는 1이 되고 

제곱근 2보다 나머지 1이 작으므로 

카운트로 +1을 해주어 출력한다.

 

이런식으로 다음 숫자들을 풀면 나머지가 제곱근보다 커지는 경우가 있는데

예를 들면  7이 그런 경우다.

 

7의 제곱근도 마찬가지로 int() 함수를 거쳐 2가 되고 

나머지는 7 - 4 로 3이 된다.

그런 경우에는 카운트에 +2를 해줘 출력을 하게 되면 정확히 규칙에 대응할 수 있게된다..

 

++ 경우의 수를 일일이 적어보는 것이 큰 의미가 없을 것이라 생각했는데 나의 큰 오산이었다...

다음부터 문제가 풀리지 않을 때는 어느정도 경우의 수를 적어보면서 규칙을 찾는 습관을 만들 생각이다.