백준 1011 Fly me to the Alpha Centauri - python

출처 :

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

1011번: Fly me to the Alpha Centauri

 

풀이 : 

T = int(input())
for i in ragne(T):
    x, y = map(int, input().split())
    
    d = y - x
    
    n = 0
    
    while True :
        if d <= n * (n+1):
            break
        n += 1   # n=5
        
    if d <= n **2:
        print(n*2 -1)
        
    else:
        print(n*2)

 

 

무척 어려운 문제다...

바로 풀이 넘어가자

 

문제에 대한 이해 :

x -> k_1 -> k_2 -> ....->k_n -> y로 가는 문제이다. 그때 이 n이 몇인지를 물어보는 문제라고 이해하면 좋다.

근데 조건은 k_1 과 k_n은 각각 1이여야한다는 것이다. 

 

또 1광년 움직였으면 다음은 1,2광년을 갈 수 있고 2광년 움직였다면 123 갈수 있고 3광년 움직였다면 234광년을 갈 수 있다.

 

그래서 이를 조금 나열 해보면

 

y-x	가는방법	반복횟수	n(답)
1	1	1	1
2	11	1	2
3	111	2	3
4	121	2	3
5	1211	2	4
6	1221	2	4
7	12211	3	5
8	12221	3	5
9	12321	3	5

10	123211	3	6
11	123221	3	6
12	123321	3	6
13	1233211	4	7
14	1233221	4	7
15	1233321	4	7
16	1234321	4	7
17	12343211	4	8
18	12343221	4	8
19	12343321	4	8

 

다음과 같은데 집중해야한다..

 

일단 빈 집이 있다고 하겠다. 

예를 들어 9를 본다면

9는 [1???1]  로 이루어져 있다. 근데 [12321]   이 9가 최대로 가질수 있는 방법은 다음처럼 12321 => 11223이렇게 더해지는 방법 밖에 불가능하다.

16의 경우도 [1234321] 이런식으로 밖에 불가능해서 답이 7개를 가진다.

 

이제 저 [] 안에 있는 값들을 최대로 더한값의 최대를 구한다음 그보다 작으면 몇개다 이렇게 내려주면된다.

그래서 1122334455 이런식으로 두번씩 반복되고 이것을 수식으로 풀면

2 * (1+2+3..) = 2* n(n+1)/2 = n(n+1) 이 나오고 이는 경계 값이 될것이다.

 

이해 안되니까 무조건 예시만 보잨ㅋ

y-x = 27이면 어떨까

n(n+1)의 n=4 이면 4*5 = 20 이므로 이는 터무늬 없다 (n=4 -> 11223344 =20)

n=5 -> 5*6 = 30 으로 바운더리 안에 들어있다. 그러니까 1122334455 이 안에 들어있는것이다.

 

그런 다음 이제 이걸 찾았으니 과연 내가 찾은 n이 앞자리 n인지 뒷자리 n인지 찾아야한다. 

앞에 설명한 예시로 보면 5를 차았는데 이게 앞에 5인지뒤에 5인지 를 찾아야한다.

 

이건 어떻게 찾냐면 1 = 1

112= 4

11223=9

1122334=16

112233445 =25

이다. 

이렇게 y-x 가 제곱인지를 기준으로 제곱보다 작다면 앞n 즉 2n-1

제곱보다 크면 그냥 2n이 답이다.

 

27 같은 경우는 n=5 -> 25보다 크므로 2*5 = 10 이므로 답이 10이다.

 

14같은 경우는 n =4 -> 16보다 작으므로 2*4-1=7 이다.

 

2.

이제 코드로 넘어가서 

입출력은 그대로 해주고 

while True (항상 돌린다)

어디까지?? 

y-x <n(n+1) 이때까지

이걸 만족하면 멈춘다. 

 

그럼 n을 구했으니까 밑에 쓴것 처럼 

n^2 보다 작으면 2n-1

n^2 보다 크면 2n 하면 된다

 

어렵다..

골드