백준 2502 (떡 먹는 호랑이)

백준 2502 (떡 먹는 호랑이)

문제 링크

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

문제 접근

할머니가 고개를 넘어가고 있습니다. 고개를 넘을 때, 할머니는 이 욕심 많은 호랑이에게 떡을 주어야 한다고 할머니를 무사히 보내준다고 합니다. 가죽으로 만들어버리고 싶습니다.. 건방진놈..

근데 또 호랑이 입장에서 생각해보면 또 인간이 자기 집을 침범하는데 떡을 통행료 삼아서 안전하게 보내준다면 나름 양반인 것 같습니다. 제가 왜 이런 말을 하느냐. 이 호랑이는 나름 메모리가 있어서 전전날 먹은 떡 + 전날 먹은 떡의 수량만큼 오늘 내지 않으면 보내주지 않는다고 합니다. 거의 산와머니마냥 이자가 불어납니다.
사실 이 말 하고 싶어서 포스팅 씁니다…. 소기의 목적을 달성하였습니다. 사실 내용 자체는 쉬운 문제라 빨리 넘어가겠습니다.

현재 산을 지나간 날 d가 주어지고, 오늘 준 떡의 수가 k일때, 첫째 날 준 떡의 수 A, 두 번째 날 준 떡의 수 B(A<=B)를 구하는 문제입니다.

일정한 규칙으로 늘어날 것 같습니다. A -> B -> A+B -> A+2B -> 2A+3B -> 3A+5B .. 이런 식으로 말이죠. 이거 보자마자 피보나치 수열이 생각났습니다. 예 모두 아실 듯 합니다.

그렇다면 d번째 날 준 떡의 수 k는 fib[d-2]xA + fib[d-1]xB = k를 만족하는 아무 A,B를 찾으면 됩니다.

b=(k-fib[d-2]*a)/fib[d-1]
    if int(b)==b :

a=1부터 시작합니다. b를 찾고, 정수라면 그냥 출력하는 형태로 코드를 짰습니다. a=1부터 시작하고, a의 가중치가 b의 가중치보다 더 낮으므로 순차적으로 탐색한다면 A<=B 조건도 만족할 듯 합니다.

소스 코드

d,k=map(int,input().split())
fib=[1]*(d+1)
for i in range(3,d+1) :
    fib[i]=fib[i-1]+fib[i-2]

for a in range(1,k+1) :
    b=(k-fib[d-2]*a)/fib[d-1]
    if int(b)==b :
        print(a)
        print(int(b))
        break

마무리하며

그냥 간단한 문제입니다. 오늘 오전에 운동 갔다 왔는데 넘 힘듭니다…….. ……..
호랑이 짤 올리고 싶어서 포스팅 써봤습니다… . .. 누가 보실지는 모르겠지만 다음 포스팅은 생각할 것이 많은 문제로 뵙겠습니다(back get some me down).