[Python] 백준 2502번 - 떡 먹는 호랑이

📌 문제 링크

• 2502번: 떡 먹는 호랑이

1. 문제 이해

Input

• 할머니가 마지막날 호랑이에게 준 떡의 개수
• 호랑이에게 떡을 준지 며칠이 되었는지

Output
첫째 날과 둘째 날에 할머니가 호랑이에게 준 떡의 개수

피보나치 수열이 적용된 문제이다.
테스트 케이스 1을 보며 이해해보자.

Input
할머니가 호랑이에게 떡을 준 일수 = 6
할머니가 마지막 날(6일)에 호랑이에게 준 떡의 개수 = 41

2. 역경

1) 시간초과

days, tteok_num = map(int, input().split())

for i in range(1, tteok_num):  
    for j in range(i, tteok_num):  
        given_tteok = [i, j]
        for k in range(2, days):
            given_tteok.append(given_tteok[k-2] + given_tteok[k-1])

        if given_tteok[days-1] == tteok_num:
            print(f"{i}\n{j}")
            break

처음 짠 코드는 떠오르는대로 바로 짜서 그런가 시간초과가 났다.

days와 tteok_num에 할머니가 산을 넘은 일수와 마지막 날에 준 떡의 개수를 입력받고 이중 for문으로 첫 날, 둘째 날 (i, j)를 임시 지정해준다. given_tteok 리스트에 피보나치 수열의 형태로 각각의 날에 준 떡의 개수를 입력한다. 그리고 if문을 통해 마지막 날의 떡의 개수와 할머니가 말해준 떡의 개수가 일치한다면 i와 j를 출력해주고 break해준다.

시간초과가 난 이유는 아마 매일의 떡 개수를 리스트에 append했기 때문인 것 같다. 우리는 마지막 날의 떡의 개수만 할머니가 말해준 떡의 개수와 일치하면 되므로 굳이 리스트에 전부 저장할 이유가 없다.

2) 런타임에러 (NamerError)

input = open(0).readline 

days, tteok_num = map(int, input().split())

for i in range(1, tteok_num):  
    for j in range(i, tteok_num):    
        a = i; b = j
        for k in range(2, days):
            temp = a + b
            a = b
            b = temp

        if temp == tteok_num:
            print(f"{i}\n{j}")
            break

시간초과 문제를 해결하기 위해 다시 코드를 수정했다. 그런데 런타임에러 (NameError)가 떠서 당황스러웠다. 내가 아는 NameError는 선언, 초기화하지 않은 변수를 사용하는 경우라고 생각했기 때문이다.

그때 눈에 들어온 게 두 번째 테스트케이스였다. 두 번째 테스트케이스를 넣으면 위와 같이 4개의 숫자가 나온다. 그래서 문제를 다시 읽어보면 다음과 같은 구절이 있다.

단, 어떤 경우에는 답이 되는 A, B가 하나 이상일 때도 있는데 이 경우에는 그 중 하나만 출력하면 된다.

즉, 내가 if문에서 break를 했기 때문에 프로그램의 종료가 아닌 위의 for문으로 올라가 다시 새롭게 순회하게 되어 두 가지 답이 전부 나오게 된 것이다. 문제를 끝까지 제대로 보자.

3. 코드 분석

days, tteok_num = map(int, input().split())

days와 tteok_num에 할머니에게 들은 일수와 마지막 날 호랑이에게 준 떡의 개수를 입력한다.

for i in range(1, tteok_num):  
    for j in range(i, tteok_num):    
        a = i; b = j
        for k in range(2, days):
            temp = a + b
            a = b
            b = temp

i와 j에 첫 날 떡의 개수와 둘째 날 떡의 개수를 임의로 지정해준다. 시간초과 이슈를 해결하기 위해 temp를 사용했다. a = i (첫 날 떡의 개수), b = j (둘째 날 떡의 개수) 이므로 temp = a + b이므로 셋째 날 떡의 개수이다. 그리고 a = b, b = temp로 지정해주고 temp가 마지막 날의 떡의 개수를 입력받을때까지 반복해준다.

테스트 케이스 1
Input : 6 41

i = 2, j = 7

• k = 2 : temp = 2 + 7 = 9, a = 7, b = 9
• k = 3 : temp = 7 + 9 = 16, a = 9, b = 16
• k = 4 : temp = 9 + 16 = 25, a = 16, b = 25
• k = 5 : temp = 16 + 25 = 41, a = 25, b = 41

k = 5 일때가 6일이 되는 날(인덱스 개념)이고 temp는 6일날의 호랑이에게 준 떡의 개수이다.

        if temp == tteok_num:
            print(f"{i}\n{j}")
            exit()

만약 temp가 할머니가 말한 마지막 날에 준 떡의 개수와 일치한다면 출력해주고 exit() 탈출한다.

4. 전체 코드

input = open(0).readline

days, tteok_num = map(int, input().split())

for i in range(1, tteok_num):  
    for j in range(i, tteok_num):    
        a = i; b = j
        for k in range(2, days):
            temp = a + b
            a = b
            b = temp

        if temp == tteok_num:
            print(f"{i}\n{j}")
            exit()