[실버 I] 2502번. 떡 먹는 호랑이

 문제 

https://www.acmicpc.net/problem/2502

2502번: 떡 먹는 호랑이

 사용 언어 

Python3

 풀이 과정 

스터디 시즌3가 시작되고 첫 모임을 위한 두 문제 중 한 문제. 사실 오늘이 모임날인지 오늘 알아서 당황했다.

그래서 시간 부족으로 이 문제를 제대로 풀지 못했는데,, 감사하게도 스터디 시간에 다시 풀어볼 기회가 생겨서 집중해서 뚱땅거려본 결과 버저비터로(?) 문제 풀기에 성공했다!

 

처음 두 숫자를 A, B라고 할 때 k번째 날의 떡 개수는 A와 B의 조합만으로 이루어진다. 그리고 그 계수는 피보나치 수열로 이루어져 있다. 따라서 일단 day값에 따라 필요한 피보나치 수열까지를 구했다.

그런데 풀면서 막혔던 부분은 3A + 5B = dduck의 A, B를 어떻게 구하나? 였다.

처음엔 이중 for문으로 풀려다가 범위를 정하기가 애매해서 다른 방법을 생각해봤다.

그러다가 5B = dduck - 3A이므로 B만 남기기 위해 양변을 5로 나눴을 때 나머지가 0이 되어야 한다는 걸 깨달았다.

 

그걸 깨닫고 while문으로 빠르게 풀었더니 초고속 맞았습니다!!

이후 스터디원의 의견을 받아 for문으로 변경해보았는데 범위가 적어서 그런지 차이는 없었다.

 

 제출 답안 

from sys import stdin
input = stdin.readline

# A B A+B A+2B 2A+3B "3A+5B" 5A+8B 8A+13B
# 2 7 9   16   25     41

day, dduck = map(int, input().split())
fibo = [1, 1] + [0 for _ in range(day - 3)]
for n in range(2, day - 1):
    fibo[n] = fibo[n - 1] + fibo[n - 2]

# day날의 dduck 개수 = (fibo[-2]A + fibo[-1]B)개
a = fibo[-2]
b = fibo[-1]
A = 1
while True:
    if (dduck - a * A) % b == 0:
        B = (dduck - a * A) // b
        break
    A += 1

print(A)
print(B)

 

 다른 사람 코드 

1. 나랑 비슷한 로직이나 D의 범위가 30까지인 걸 고려해 일단 30까지의 피보나치 수열을 구했다.

항상 베스트(?) 답변들을 보면 먼저 문제에서 제시한 최대 범위까지 구하는 게 의문이었는데 확실히 더 빠른 것 같다...

import sys

D, K = map(int, sys.stdin.readline().split())

fibo = [0] * 31

fibo[1] = 1
fibo[2] = 1

for i in range(3, 31):
    fibo[i] = fibo[i-1] + fibo[i-2]

a_coe = fibo[D-2]
b_coe = fibo[D-1]

a = 0
b = 0
while True:
    a += 1
    if (K - a_coe*a) % b_coe == 0:
        b = int((K - a_coe * a) / b_coe)
        break
print(a)
print(b)