백준 2502: 떡 먹는 호랑이 [Python 파이썬 / 브루트포스]

백준 2502: 떡 먹는 호랑이

🥸 문제 분석

D번째 날에 호랑이에게 준 떡의 개수를 이용해
첫번째 날과 두번째 날에 호랑이에게 준 떡의 개수를 구해야 한다.

☝️ 문제 풀이

첫번째 날에는 A개, 두번째 날에는 B개를 주는 게 문제의 조건이다.
세번째 날부터 호랑이에게 주게 되는 떡의 개수를 순차적으로 적어보면

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

즉 A는 3번째 날부터 차수가 1, 1, 2, 3 .. 의 형태로 변하고 있고
B는 3번째 날부터 차수가 1, 2, 3, 5 .. 의 형태로 변하고 있다.

사실 이미 떡의 개수가 누적되는 식부터 감이 오지만,
두 차수 모두 피보나치 수열의 형태이다.
A와 B의 차수도 피보나치 수열의 형태로 늘어나고 있다.

즉, A와 B의 차수로 사용하기 위해 피보나치 수열을 하나 만들어주자. 다양한 방법이 있지만 아래처럼 직관적인 코드를 짤 수도 있다.

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

이제 구해놓은 차수를 활용하여 답을 구하면 된다.
앞서 순차적으로 적었던 식을 통해 확인할 수 있듯,
A와 B의 차수는 fibo[D - 3], fibo[D - 2]와 같다.
A, B의 차수는 D값에 의해 바로 정해지기 때문에,
이제 A, B로 이루어진 식을 만족시키는 답만 찾아내면 된다.

백준의 예시에 적용해보자.
D = 6, K = 41 의 경우이다.
그럼 A, B의 차수는 fibo[D-3], fibo[D-2]로,
각각 3, 5이다.
즉, 3A + 5B = 41을 만족시키는 A와 B를 구하면 된다.
A에 숫자를 1부터 대입해보면서 순차적으로 탐색하는 쉬운 방법이 있다.

a_d, b_d = fibo[D - 3], fibo[D - 2]
for A in range(1, K // a_d + 1):
    rest = K - (A * a_d)
    if rest % b_d == 0:
    	B = rest // b_d
        print(f'{A}\n{B}')
        break

A를 1에서 대입 가능한 수까지 증가시키면서,
A의 차수와 A를 곱한 값을 K에서 뺀 수가
B의 차수로 나누어 떨어진다면, B를 구할 수 있다.
A <= B인 A와 B를 구해서 출력하면 정답.