[백준][Python] 2502번: 떡 먹는 호랑이

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

 

 

어제 받은 떡과 그저께 받은 떡의 개수를 더한 만큼의 떡을 받아야 한다고 하는데

이것을 수식으로 표현해보면

Day[n] = Day[n-1] + Day[n-2]가 된다.

 

즉, 피보나치 수열의 형태로 빵을 갈취해간다.

 

주어지는 입력은 넘어온 총 날과 그 날 호랑이에게 준 떡의 개수 K이고

출력은 위 입력이 나오도록 하는 첫째날과 둘째날 준 떡의 개수를 출력해야 한다.

 

정리하면 Day[D] = K 가 되는 피보나치 수열의 형태의 0번째 항과 1번째 항을 찾으면 된다.

 

일단 가장 먼저 동적 프로그래밍을 적용했다.

 

동적 프로그램이란 자주 사용되는 값들을 저장해서 재사용해 문제의 소요 시간을 줄이는 방법이다.

 

예를 들어 피보나치 수열의 어느 값을 구한다고 할 때

 

만약 재귀 함수로 구한다면 어느 값의 크기에 따라 수만개의 F[0]과 F[1]을 구하게 될 것이다.

 

이에 동적 프로그래밍은 이러한 F[0]과 F[1]을 구하는 과정을 최소화 한다.

 

배열에 F[2], F[3], F[4], F[5], ... 를 밑에서부터 올라가며 채우는 것이다.

 

이 경우 F[n]을 반복문 한번에 만들어낼 수 있게 된다.

 

 

그래서 무식하게 A, B를 2중 for문을 돌며 K 값을 구해 비교하게 해보았다.

 

원래는 시간초과가 뜨는지 확인해보려고 이렇게 했는데

 

바로 성공이 떠버렸다

 

코드보기

from sys import stdin

def get_K(D, A, B):
    dp = [0 for _ in range(D + 1)]
    dp[1] = A
    dp[2] = B
    for i in range(3, D + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[D]


D, K = map(int, stdin.readline().split())
end = False

for i in range(1, K):
    for j in range(i, K):
        if get_K(D, i, j) == K:
            print(i)
            print(j)
            end = True
            break
    if end:
        break

 

그래도 최적화 할 수 있는 부분은 최적화 해보자.

 

무려 800ms 라는 시간이 소요되었다

아마 K의 범위를 생각해보면 시간초과를 띄우는 반례가 존재할 것 같다.

 

 

피보나치 수열을 분석해보자

 

N	F[1] = A, F[2] = B
3	A + B
4	(A + B) + B = A + 2B
5	(A+2B) + (A+B) = 2A + 3B
6	(2A+3B) + (A+2B) = 3A + 5B
7	(3A+5B) + (2A+3B) = 5A + 8B
8	(5A+8B) + (3A+5B) = 8A + 13B
9	(8A+13B) + (5A+8B) = 13A + 21B
10	(13A+21B) + (8A+13B) = 21A + 34B
11	(21A + 34B) + (13A+21B) = 34A + 55B

 

이렇듯 F[i] 를 A와 B에 대한 식으로 구할 수 있다.

 

만약 A를 정해준다면 k를 구하기 위한 B의 값을 금방 정할 수 있게 된다.

 

예제 1번을 보면 D = 6이고 k = 41이다.

 

이때의 식은 F[6] = 3A + 5B 이다.

 

즉 B = (k - 3A) / 5 이고 k값을 대입해주면

B = (41 - 3A) / 5 가 된다.

 

여기서 1<=A<=B를 만족하는 정수 B를 찾으면 된다.

 

A를 1부터 증가시키면서 살펴보자

A = 1 -> B = (41-3)/5 = 38 / 5 (분수)

A = 2 -> B = (41 - 6) / 5 = 35 / 5 -> 7

이로써 A = 2, B = 7이라는 결과값을 얻을 수 있다.

 

B가 정수인 것은 어떻게 판단해야 할 까?

 

그것은 분모로 분자를 나누었을 때 나누어 떨어지면 된다.

즉 (41 - 3A) % 5 == 0 이면 정수가 된다.

 

이때의 (41 - 3A) / 5 값이 B값이 된다.

 

그럼 이제 B값이 A값보다 큰지만 확인하면 되는데...

이미 조건을 만족하는 A, B가 존재한다고 나와있다.

즉, B는 A에 반비례하는 상태이니 B가 A보다 작아지기 전에 주어진 답을 만나서 반복문을 탈출하게 될 것이다.

 

따라서 B와 A를 비교할 필요가 없어진다.

 

코드 보기

from sys import stdin

def Fibo(D):
    dp = [[0, 0] for _ in range(D + 1)]
    dp[1] = [1, 0]
    dp[2] = [0, 1]
    for i in range(3, D + 1):
        dp[i][0] = dp[i - 1][0] + dp[i - 2][0]
        dp[i][1] = dp[i - 1][1] + dp[i - 2][1]

    return dp[D]

D, K = map(int, stdin.readline().split())

dp = Fibo(D)

for A in range(1, K):
    if (K - dp[0] * A) % dp[1] == 0:
        B = (K - dp[0] * A) // dp[1]
        print(A)
        print(B)
        break

 

매우 큰 속도 향상을 얻을 수 있었다.