[백준] 1904 다이나믹 프로그래밍 01타일

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

 

요즘 백준허브를 이용하느라 글을 잘 안썼는데

 

오늘 알게된 새로운 사실을 기록하려고 포스팅 하나 씁니다 ! 

 

import sys



N = int(input())
dp = [0] * (N+1)
dp[1] = 1
dp[2] = 2
for i in range(3,N+1):
    dp[i] = dp[i-1] + dp[i-2]

print(dp[N] %  15746)

처음 코드

 

점화식 거의 10분?도 안돼서 발견하고 , 이제 문제 유형 안봐도 DP인걸 딱 알겠어서

좀 늘었구나 했는데

당황을 안할수가 없었다

1. 시간초과는 죽어라 많이 봤어도 메모리 초과는 한번도 못 봤기에

2. 생각해보니 N이 1이나 2면 반복문 범위에 문제가 생김

문제 조건에 이런게 있다

 

첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

 

이유는 다른 언어랑 다르게 파이썬의 Int는 4바이트로 고정되지 않고 , 숫자가 더 커질수록 메모리를 많이 차지한다고 한다 

 

그래서 ,, N이 백만에 근접하게 되면 메모리를 너무 많이 잡아먹게 돼서 오류가 뜨는 것

 

그래서 해결한 방법 

=> "배열 안에 수를 저장할 때 부터 수를 작게 저장하자!"

 

어차피 ,, dp[i-2]가 백만오천이라고 해도 ,dp[i-1]의 값이 얼마인지 구체적으로 중요하지 않다

 

어차피 문제에서 요구하는건 " 저 수로 나눈 나머지"를 출력하기만 하면 되기에

 

해결 코드

import sys



N = int(input())
dp = [0] * (N+1)

if N == 1:
    print(1)
elif N == 2:
   print(2)
else:
 dp[1] = 1
 dp[2] = 2
 for i in range(3,N+1):
     dp[i] = (dp[i-1] + dp[i-2]) % 15746
    

 print(dp[N])

1. N == 1 / N == 2에 대한 예외처리

 

식은 , dp[i-1]에서 끝에 1을 붙이거나 , dp[i-2]에서 끝에 00을 붙이거나로 정리가 돼서

dp[i] = dp[i-1] + dp[i-2] 

유명한 피보나치 수열 식을 다른 형식으로 바꾼 문제였다