백준 - 1904번

import sys
n = int(sys.stdin.readline())

dp1 = []
dp2 = []

dp1.append(1)
dp1.append(2)
cnt = 0

if n == 1:
    print(1)

elif n == 2:
    print(2)

for cnt in range(n):
    dp1.append(dp1[0] + dp1[1])
    dp2.append(dp1[1])
    dp2.append(dp1[2])
    cnt += 1
    if cnt == n-2:
        print(dp1[2])
        break
    dp1.clear()

    dp2.append(dp2[0] + dp2[1])
    dp1.append(dp2[1])
    dp1.append(dp2[2])
    cnt += 1

    if cnt == n-2:
        print(dp2[2])
        break
    dp2.clear()

Dynamic Programming으로 메모리 부족 오류가 떠서 3칸의 배열을 두 개만 쓰는 방법을 생각했다.

3칸짜리 배열 두 개를 서로 복사하면서 초기화를 반복하는 것이다.

답은 정상적으로 나온다.

이번엔 시간 초과 오류가 떠버렸다.

결국 정답은 아래와 같았지만 정말 어이없는 부분이었다.

 

import sys

n = int(sys.stdin.readline())

dp = [0] * 1000001
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])

15746으로 나눈 나머지를 출력하는 이유가 있었다.

아주 큰 수를 연산할 경우 dp메모리에 값을 넣을 때 메모리 누수 오류가 생길 것이다.

따라서 print안에 최종 값 dp를 나누는 것이 아니라 연산 결과마다 나머지 연산을 해줘야 하는 것이다.

그러면 값이 아무리 크더라도 15745 밖에 들어가지 않을 것이다. 메모리 부족 오류에서 눈치챘어야 했다.

이번 문제는 규칙 자체는 피보나치수열과 동일해서 어렵지 않았지만 위에 배열 3개짜리를 사용하면서 시간 복잡도를 극도로 줄이기 위해 찾아보면서 도움이 된 부분들이 많다.

메모리 부족을 눈치채는 좋은 교훈도 얻었으니 만족할 만한 문제이다!