2502 - 떡먹는 호랑이

• 첫째날 둘째날 얼마나 줬는지 구하는게 목표!
• 첫째날 = a
• 둘째날 = b

1	2	3	4	5	6	7	8
a	b	a + b	a + 2b	2a + 3b	3a + 5b	5a + 8b	8a + 13b

1	2	3	4	5	6	7	8
(1,0)	(0,1)	(1,1)	(1,2)	(2,3)	(3,5)	(5,8)	(8,13)

규칙을 찾아보면 4번째부터 규칙이 보이기 시작한다.

예를 들어 5번째 날을 보면 (2,3)으로 표현 가능한데

이는 4번째 날의 (1,2)에서

• 두번째항이 5번째 날의 첫번째항
• 첫번째+두번째 = 5번째 날의 두번째항

n-1 번째 날(a, b)라면

n번째 날은 (b, a+b) 가 될것이다.

이런식으로 dp에 쭉 저장을 하면

dp[day][0] 은 a의 계수

dp[day][1] 은 b의 계수가 된다.

Ex)

만약 6번째날 41개의 떡을 주었다면

6번째날 = 3a + 5b 이다.

3a + 5b = 41 을 만족하는 정수 a, b를 구하면 답이다!(단, a ≤ b )를 만족해야한다.

브루트포스로 하나씩 찾아줬다.

a = 1일때 41 - 3*1 이 5로 나누어떨어지는지 확인하고 안나눠떨어지면 a++

a = 2일때 41 - 3*2 = 35 이고 35는 5로 나누어떨어지기 때문에

• first_day에 2를 저장, second_day에는 35//5인 7을 저장.

day, ddeok = map(int,input().split())

dp = [[0]*2 for _ in range(day+1)]

dp[1][0] = 1
dp[1][1] = 0 

dp[2][0] = 0
dp[2][1] = 1

dp[3][0] = 1
dp[3][1] = 1

for i in range(4, day+1):
    dp[i][0] = dp[i-1][1]
    dp[i][1] = dp[i-1][0] + dp[i-1][1]

first_day = dp[day][0]
second_day = dp[day][1]

loop_num = ddeok // first_day #떡 개수를 a의 계수로 나누면 최대 loop 할수있는 횟수이다.

for i in range(1, loop_num+1):
    remain_ddeok = ddeok - (first_day*i)
    if remain_ddeok % second_day == 0:
        second_day = remain_ddeok//second_day
        first_day = i
        break

print(first_day)
print(second_day)