[백준]2502 떡 먹는 호랑이(Python)

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

2502번: 떡 먹는 호랑이

 

문제 접근

 

d[n] = d[n-1] + d[n-2]

n, d[n]이 주어질 때, 구해야 하는 값은 d[0]와 d[1]

 

첫번째 날 A개, 두번째 날 B개라면,

 

3번째 날: A + B

4번째 날: B + (A + B) =  A + 2B

5번째 날: (A + B) + (A + 2B) = 2A + 3B

6번째 날: (A + 2B) + (2A + 3B) = 3A + 5B

 

계수의 변화를 살펴보면 A의 경우 1, 1, 2, 3...

B의 경우 1, 2, 3, 5...식으로 변하고 있다.

 

이를 이용해 피보나치 수열을 만들어 보면,

fibo = [1, 1]
for _ in range(D - 3):
	fibo.append(fibo[-2] + fibo[-1])
# D=6 => fibo = [1, 1, 2, 3, 5]

 

D = 6, K = 41 이면,

A의 계수는 fibo[D-3] = 3

B의 계수는 fibo[D-2] = 5

=> 3A + 5B = 41 

 

A는 1부터 K//A의 차수까지 가능하므로 반복문을 작성해 보면,

x, y = fibo[D-3], fibo[D-2]
for A in range(1, K//x + 1):
    remain = K - (x*A)
    if remain % y == 0:
        B = remain // y
        print(A)
        print(B)
        break

 

코드

D, K = map(int, input().split())

fibo = [1, 1]
for _ in range(D - 3):
	fibo.append(fibo[-2] + fibo[-1])
# fibo = [1, 1, 2, 3, 5, 8, 13, ...]
# print(fibo)

x, y = fibo[D-3], fibo[D-2]
for A in range(1, K//x + 1):
    remain = K - (x*A)
    if remain % y == 0:
        B = remain // y
        print(A)
        print(B)
        break

 

회고

 

계수가 피보나치 수열임을 확인하고 이를 fibo 리스트로 만들어 저장한 후 각각의 계수가 가진 값을 일반화하는 과정이 어려웠다. 반복문의 범위를 A를 기준으로 잡고(B로 해도 상관 없음) 그리고 만약 B가 해당 계수로 나누어떨어질 때 B가 정해진다는 것이 핵심!!

 

반복문을 작성하는 과정이 어제 푼 프로그래머스 카펫(완전 탐색)과 비슷한 느낌..?