[🥈1 / 백준 2502 / 파이썬] 떡 먹는 호랑이

 

2502번: 떡 먹는 호랑이

 

문제

하루에 한 번 산을 넘어가는 떡 장사 할머니는 호랑이에게 떡을 주어야 산을 넘어갈 수 있는데, 욕심 많은 호랑이는 어제 받은 떡의 개수와 그저께 받은 떡의 개수를 더한 만큼의 떡을 받아야만 할머니를 무사히 보내 준다고 한다. 

예를 들어 첫째 날에 떡을 1개 주었고, 둘째 날에는 떡을 2개 주었다면 셋째 날에는 1+2=3개, 넷째 날에는 2+3=5개, 다섯째 날에는 3+5=8개, 여섯째 날에는 5+8=13개를 주어야만 무사히 산을 넘어갈 수 있다. 

우리는 산을 무사히 넘어온 할머니에게 오늘 호랑이에게 몇 개의 떡을 주었는지, 그리고 오늘이 호랑이를 만나 떡을 준지 며칠이 되었는지를 알아내었다. 할머니가 호랑이를 만나서 무사히 넘어온 D째 날에 준 떡의 개수가 K개임을 알 때, 여러분은 할머니가 호랑이를 처음 만난 날에  준 떡의 개수 A, 그리고 그 다음 날에 호랑이에게 준 떡의 개수 B를 계산하는 프로그램을 작성하시오. 이 문제에서는 항상 1≤A≤B 이다.  

예를 들어 여섯 번째 날에 산을 무사히 넘어온 할머니가 호랑이에게 준 떡이 모두 41개라면, 호랑이를 만난 첫 날에 준 떡의 수는 2개, 둘째 날에 준 떡의 수는 7개이다. 즉 셋째 날에는 9개, 넷째 날에는 16개, 다섯째 날에는 25개, 여섯째  날에는 41개이다. 따라서 A=2, B=7 이 된다. 단 어떤 경우에는 답이 되는 A, B가 하나 이상일 때도 있는데 이 경우에는 그 중 하나만 구해서 출력하면 된다.

입력

첫째 줄에는 할머니가 넘어온 날 D (3 ≤ D ≤ 30)와 그 날 호랑이에게 준 떡의 개수 K (10 ≤ K ≤ 100,000)가 하나의 빈칸을 사이에 두고 주어진다. 

출력

첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤A≤B)가 존재한다. 

 

예제 입력 1 6 41	예제 출력 1 2 7
예제 입력 2  7 218	예제 출력 2  10 21

 

풀이

 

다이나믹 프로그래밍과 브루트 포스 알고리즘이 동시에 적용되는 문제이다.

 

bottom-up 방식이지만 일반적인 동적 계획법 문제와는 다르게 초기값이 없다.

따라서 브루트 포스 알고리즘을 통해 알맞은 답이 나올 때까지

반복적으로 다이나믹 프로그래밍을 실시하며 초기값을 구해야 한다.

 

다이나믹 프로그래밍을 적용하기 위해 메모이제이션 할 배열을 dp라고 하고,

dp[0], dp[1]을 각각 A,B 라고 하자.

우리가 구해야 할 것은 dp[D-1] 이다.

 

A, B (1≤A≤B) 이므로 A와B의 초기값은 1,1 이다.

여기서 차근차근 올려나갈 것이다.

 

수행해야 할 다이나믹 프로그래밍은 간단하다.

dp[n] = dp[n-1] + dp[n-2] 이다.

 

위 연산을 수행하다가, dp[D-1] 이 원래 목표값인 k와 일치한다면

프로그램을 종료하고 A,B 를 출력해주면 된다.

 

만약 dp[D-1]이 원래 목표값인 k보다 작다면

A와 B의 차가 적은 것일테다.

A와 B의 차가 클수록 수가 증가하는 폭이 커지기 때문이다.

따라서 폭을 증가시키기 위해 B의 값을 1씩 증가시키도록 하자.

 

만약, dp[D-1]이 k보다 크다면 A와 B의 차가 큰 것이다.

하지만 중간에 답이 있었다면 이미 프로그램이 종료되고 정답인 A와 B를 구할 수 있었을 것이다.

따라서 새로운 경우의 수를 대입하기 위해 A를 1 증가시켜주자.

여기서 B는 A이상이어야 하므로 증가된 A값으로 대입해주면 된다.

 

d,k = map(int,input().split())

dp = [0 for i in range(d)]
dp[0],dp[1] = 1,1

while(True):
    for i in range(2,d):
        dp[i] = dp[i-1]+dp[i-2]
    
    if dp[d-1] == k:
        print(dp[0],dp[1],sep="\n")
        break
    elif dp[-1] > k:
        dp[0] += 1
        dp[1] = dp[0]
    else:
        dp[1] += 1