[알고리즘] 백준1904 - 01타일 파이썬

 

 

일단 이 수많은 삽질의 흔적이 보이십니까? 

보고 모른 척해주십시오...

일단 이 문제는 DP(Dynamic Programing)이지만 로직 자체는 피보나치 수열이랑 똑같습니다. 문제를 쪼개서 생각하고 작은 문제가 맞으면 큰 문제까지 잘 적용이 되냐 안되냐를 물어보는 문제입니다.

 

일단 오답 코드 먼저 보시죠

배열을 이용한 피보나치

import sys
input = sys.stdin.readline

def binary(n):
    arr = []
    arr.append(0)
    arr.append(1)
    arr.append(2)
    
    for i in range(3, n+1):
        arr.append(arr[i-1] + arr[i-2])
    
    return arr[n] % 15746

n = int(input().strip())
print(binary(n))

 

재귀를 이용한 피보나치

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def binary(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        return (binary(n-1) + binary(n-2)) % 15746

n = int(input().strip())
print(binary(n))

 

틀린 이유

로직 자체는 다 맞습니다. 한 가지를 제외하고....

파이썬에서는 inf 거의 무한대까지 지원하지만 숫자가 매우 커질 경우 여기서는 (10^6)을 넣죠?  (이거 그냥 돌릴 때 한 몇만 때려 넣고 메모리 초과!, 시간 초과! 이러는 거 같은데 사악하다... 사악해!! 독하다 독해!)

그래서 이 숫자가 커질수록 계산할 때 시간을 많이 잡아먹어서 시간 초과가 나는 거 같았습니다. 그리고 숫자가 커질수록 그 값을 저장하는 데 필요한 메모리도 증가해서 메모리 초과가 나는 거 같습니다.

 

필요한 아이디어

여기서 괜히 마지막에 모듈 연산을 통해 % 15746을 하라는 게 아닙니다. 

전 여기서 각 배열에서 이제 15746보다 크면 무조건 그냥 모듈로 나눴습니다. "이걸 왜 함?"이라고 하면 위에 틀린 이유를 다시 읽어보세요.

 

정답 코드

import sys
input = sys.stdin.readline

def binary(n):
    arr = [0] * (n+3)
    arr[0] = 0
    arr[1] = 1
    arr[2] = 2
    
    for i in range(3, n+1):
        arr[i] = arr[i-1] + arr[i-2]
        if arr[i] > 15746:
            arr[i] = arr[i] % 15746
    
    return arr[n] % 15746

n = int(input().strip())
print(binary(n))

 

원래는 n + 1인데 이것도 인덱스 에러가 나서 기본으로 우리가 최소 3개의 배열은 가지고 있어야 해서 그냥 저렇게 넣었습니다. 솔직히 저렇게 안하고 예외로 처리하셔도 됩니다.