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

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

2502번: 떡 먹는 호랑이

아이디어

• 첫째날 둘째날을 a, b로 두고 D와 K를 가지고 점화식을 만들어 보자
• 예) D가 4면 a, b, a+b, a+2b, 2a+3b, 3a+5b=> K=a+2b
• DP배열을 2차원배열로 만들어 a에 곱해지는 값과 b의 곱해지는 값을 저장함

구현

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

d = [0] * 31 

d[1] = (1,0) # 첫째날 1a + b
d[2] = (0,1) # 둘째날 0a + 1b

for i in range(3, D+1): # D번째날 떡의 갯수
    d[i] = (d[i-1][0] + d[i-2][0], d[i-1][1] + d[i-2][1])

# D번째 날의 a와 b의 계수 
a = d[D][0]
b = d[D][1]

n,m = 1,1 # a와 b의 값
# 브루트포스 알고리즘
while True:
    if a*n + b*m == K: # a와 b의 값을 찾으면 출력 후 break
        print(n)
        print(m)
        break
    elif a*n + b*m < K: # a와 b값이 k 보다 작다면 b의 값을 하나키움 
        m += 1
    else: # 아직 찾지 못했으면 a는 +1 b는 1 
        n += 1
        m = 1

마무리

• 피보나치 수열을 미리 알고있어 쉽게 풀린 문제인듯