[ BOJ / Python ] 2502번 떡 먹는 호랑이

이번 문제는 피보나치수열의 변형 문제였다. 패턴을 찾기 위해 미지수 a와 b를 대입해보았다.

• d가 6이라면,
  -> k[0]=a
  -> k[1]=b
  -> k[2]=a+b
  -> k[3]=a+2b
  -> k[4]=2a+3b
  -> k[5]=3a+5b
  이러한 형태가 나타난다.

미지수가 2개이기 때문에 고민을 조금 하였고, 구하고자 하는 k를 구성하는 a의 갯수와 b의 갯수를 이용하여 전체 수를 대입해보기로 하였다.

• a의 갯수를 ac, b의 갯수를 bc로 정의하였고, for문을 통하여 d번째 k의 ac, bc를 구하였다.
• 식을 세워보면 k=ac*a+bc*b이다. a에 1부터 100,000까지 대입해보면서 b의 값을 구하였다.
• b=(k-ac*a)/bc가 되고 a에 임의의 수가 들어가게 된다면 b를 제외한 모든 수가 주어지는 셈이다.
• b가 타당한 수라는 것을 확인하기 위해서는 %연산의 결과값이 0이 나와야 한다. for문 안에 (k-ac*a)%b=0이라는 조건문을 넣어 이 조건에 만족하면 값을 출력하고 프로그램을 종료시킨다.

처음에 문제에 접근할 때에는 k=ac*a+bc*b식을 정리하지 않고 사용하여 이중 for문을 사용하였고 이 때문에 시간초과가 발생하였다. k=ac*a+bc*b식을 (k-ac*a)%b=0로 정리하고 a에만 값을 하나씩 대입하며 적합한 b를 찾아내는 방식으로 시간을 단축하였다.

d,k=map(int, input().split())
ac=1
bc=0
for i in range(d-1):
    ac, bc=bc, ac+bc
for a in range(1, 1000000):
    if (k-(ac*a))%bc==0:
        print(a, (k-(ac*a))//bc, sep="\n")
        break