[백준 1904번] DP로 피보나치 구현

DP 문제를 이제 2~3개 정도 풀어본 것 같은데 드디어 감이 좀 잡히려고 한다.

아직 쉬운 것만 풀어봐서 그럴진 모르겠지만 감이라도 잡힌 것에 감사하고 있다. 풀다보면 늘 거라고 생각한다.

 

1 1   1
2 2   00 11
3 3   001 100 111
4 5   0000 0011 1001 1100 1111
5 8   00001 00100 10000 00111 10011 11001 11100 11111
6 13  000000 000011 001001 001100 100001 100100 110000 001111 100111 110011 111001 111100 111111 
7 21  0000001 0000100 0010000 1000000 0000111 0010011 0011001 0011100 1000011 1001001 1001100 1100100 1110000 1100001 0011111 1001111 1100111 1110011 1111001 1111100 1111111

대충 이런 식으로 7까지 일단 무식하게 풀어봤다.

역시 답 자체가 피보나치였다. 처음엔 이 계산도 잘못해서 분명 패턴이 있는데 뭐지? 싶었다. 그냥 한두개 빼먹은 거였다.

 

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

첫 시도는 메모리 초과였다. 사실 이것도 구글링으로 푼 거라 d의 길이를 최대값 1,000,000 + 1로 놨다.

이 코드로 메모리 초과가 뜨지 않으려면 계산 자체를 15746로 나눠줘야 한다. input에 큰 값이 들어가면 메모리가 초과하기 때문이다.

n = int(input())
d = [0,1,2]
for i in range(3,n+1):
    d.append((d[i-1]+d[i-2])%15746)
print(d[n])

마지막으로 제출한 코드.

위 코드에서 d와 d에 입력하는 방식만 달라졌기 때문에 메모리나 시간 차이는 거의 없었다.

오히려 메모리는 이 방법이 더 많이 든다.

 

나름 동적계획법1 중에서도 단계 3이길래 덜 긴장했는데 좀 더 긴장할 필요가 있겠다.

DP문제가 나오면 자신 있게 풀도록 연습해야겠다.