떡 하나 주면 안잡아먹지 어흥

BOJ 2502 - 떡 먹는 호랑이 링크
(2022.10.18 기준 S2)
(치팅하면 잡아먹지)

문제

하루에 한 번 산을 넘어가는 할머니는 호랑이에게 떡을 주어야만 산을 넘어갈 수 있다. 호랑이는 떡을 어제 받은 떡의 개수와 그저께 받은 떡의 개수를 더한 만큼의 떡을 받고자 한다.
D째 날에 준 떡의 개수가 K개라면, 첫째 날에 준 떡의 개수 A와 둘째 날에 준 떡의 개수 B를 계산하여 출력

알고리즘

떡의 개수 방정식은 피보나치 수열로 하여금 계수를 이룬다.
먼저 피보나치 수열을 DP로 구한 다음, 방정식에 따라 A와 B를 일일이 찾아야 한다. (브루트포스)

풀이

날에 따른 떡의 개수는 다음과 같다.

잘 보면 A는 넷째 날부터, B는 셋째 날부터 피보나치 수열을 이루는 것을 알 수 있다.
그러면 방정식을 세우면?

K = fib[D - 3] * A + fib[D - 2] * B (D >= 4)

셋째 날은 A + B = K 이므로 예외 케이스로 두어 출력하면 된다.

그럼 일단 피보나치 수열부터 dp로 구하자.
dp의 크기는 편의상 D로 두고 점화식은 fn = fn-1 + fn-2 이므로 그대로 옮겨서 구하자.

dp = [0] * D
dp[1] = 1; dp[2] = 2
for i in range(3, D):
	dp[i] = dp[i - 1] + dp[i - 2]

그리고 A와 B의 계수인 fib[D - 3]과 fib[D - 2]를 이용하여 가능한 A와 B를 일일이 찾아가면 된다.

코드

import sys; input = sys.stdin.readline

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

if D == 3: # 셋째 날은 A + B = K 이므로 아무 수나 출력 후 프로그램 종료
    A = K // 2
    print(A)
    print(K - A)
    exit()

# 떡의 개수 K는 첫째 날 떡 A와 둘째 날 떡 B가 피보나치 수열로 하여금 계수를 이룬다.
# K = fib[D - 3] * A + fib[D - 2] * B (D >= 4)
# 피보나치 수열부터 dp로 구하자.
fib = [0] * D
fib[1] = 1; fib[2] = 2
for i in range(3, D):
    fib[i] = fib[i - 1] + fib[i - 2]
a = fib[D - 3]; b = fib[D - 2] # 계수를 따로 저장

# a와 b를 이용하여
# 가능한 A, B를 일일이 찾는다. (브루트포스)
for A in range(1, 100001):
    S = a * A
    for B in range(1, 100001):
        S += b
        if S == K: # 합이 K와 같아지면 A와 B를 출력 후 프로그램 종료
            print(A)
            print(B)
            exit()
        if S > K: # 합이 K보다 커지면 A를 다시 설정
            break

여담

초급자의 필수 코스인 피보나치 dp와 브루트포스가 적절하게 섞인 아주 좋은 문제였던 것 같다.
거기다가 A와 B가 D에 따라 계수가 피보나치를 이룬다는 것을 알아채야 하는 약간의 관찰력까지.