[BOJ][Python]15841번 풀이

가끔 다국어 문제가 나오면 약간 움찔하게 되는 것 같습니다. 문제에 본질에 집중하려고 읽다보면 어느새 문제 전체를 해석하고 있는 이상한 짓을 가끔 하게 됩니다. 해당 문제의 경우 본질은 피보나치 수열을 dp로 구현하는 문제이기 때문에 해보셨던 적이 있으신 분이라면 너무 간단한 문제라고 생각하실 것 같네요.

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

15841번: Virus Outbreak

#fibonacci
table = [0 for _ in range(491)]
table[1] = 1
for i in range(2, 491):
    table[i] = table[i-1]+table[i-2]
while 1:
    h = int(input())
    if h == -1:
        break
    print(f'Hour {h}: {table[h]} cow(s) affected')

간단하죠? 보통 dp 피보나치 수열 문제는 호출 횟수를 물어보는 문제가 대부분이었던 것 같은데 이번엔 그냥 수열의 합을 물어보기 때문에 미리 테이블을 구성해놓고 호출만 시켜도 아무 문제 없습니다. 테이블 범위도 작으니 까짓거 490까지 모든 합을 미리 구해서 구성해놓는다면 훨씬 빠르게 돌아가도록 만들수도 있겠죠.