[알고리즘] 1904: 01타일 메모리초과?

 

 

1904번: 01타일

 

#01타일 
import sys

n = int(sys.stdin.readline())
dp = [0] * (n - 1)

def tile_zero(num):
    for i in range(num - 1):
        if i == 0:
            dp[i] = 1
            
        if i == 1:
            dp[i] = 2
            
        if i >= 2:
            dp[i] = dp[i - 1] + dp[i - 2]
            
    return dp[-1]

print(tile_zero(n))

 

n  = int(input())
dp =[0] * 1000001
dp[1] =1
dp[2] = 2
for i in range(3, n+1):
	dp[i] = (dp[i-2]+dp[i-1]) % 15746
print(dp[n])

 

숫자가 int를 최대값을 넘어가면은 메모리를 엄청 많이 먹는다 
매순간 나눗셈을 해서 저장하면은 21억이 넘어감.... 

 

다만, 문제의 n이 최대 1,000,000 이므로 계산 중간 int의 범위를 벗어나는 경우가 생기므로

맨 마지막 결과가 아닌 중간중간 %15746을 해야한다.

 

왜 15746인가???는 아무도 모른다

흐흐히히하하하하

그러게 왜 타일을 바꾸냐 참나