[Baekjoon] 2502_떡 먹는 호랑이

Silver I

문제(출처: https://www.acmicpc.net/problem/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)가 존재한다. 

 

 

문제 풀이

- my solution

import sys

if __name__=='__main__':
    D,K=map(int, sys.stdin.readline().split()) # 넘어온 날, 떡의 개수

    arr=[[1,0],[0,1]] 

    for i in range(2,D):
        arr.append([arr[i-1][0]+arr[i-2][0], arr[i-1][1]+arr[i-2][1]])

    a_temp=arr[-1][0]
    b_temp=arr[-1][1]
    a=1
    b=-1

    while True: # 첫 날, 둘째 날 떡의 개수 구하기
        temp=K-(a_temp*a)
        if temp%b_temp==0:
            b=temp//b_temp
            break
        else:
            a+=1

    print(a) # 첫 날
    print(b) # 둘째 날

 

첫날 호랑이에게 준 떡의 수를 a라 하자. 둘째 날에 호랑이에게 준 떡의 수를 b라 하자.

그럼 셋째 날은 a+b, 넷째 날은 b+(a+b)=a+2b, 다섯째 날에는 (a+b)+(a+2b)=2a+3b, 여섯째 날에는 (a+2b)+(2a+3b)=3a+5b가 된다.

 

만약 주어진 예제와 같이 입력이 할머니가 넘어온 날=6, 그날 호랑이에게 준 떡의 개수=41이라고 한다면 

3a+5b=41이 되는 a와 b의 값을 찾으면 되는 것이다.

 

위와 같이 구했을 때 넘어온 날이 늘어나도 a와 b의 조합으로만 문제를 해결할 수 있다는 것을 알 수 있다.

 

그래서 리스트를 선언하여 [a의 개수, b의 개수]를 저장하였다.

 

답이 여러 개가 존재할 수 있지만 그중 하나면 구해서 출력하면 되는 것이므로 반복문을 돌려 a와 b의 값이 구해지면 중단하고 답을 출력해준다.

 

답을 구할 때, a의 값을 기준으로 구하였다. a가 1일 때부터 시작하여 그날 준 떡의 개수 - [a의 개수 * a(첫날 떡 개수)]를 구한 후 앞에서 구한 값이 b의 개수로 나누어 떨어지는지 확인하여 나누어 떨어지면 중단하도록 구현하였다.

---

생각🤔

 

규칙을 찾으면 쉽게 해결할 수 있는 문제였다.

다이나믹 프로그래밍 뿌시기 -!

 

---