오늘의 문제
https://www.acmicpc.net/problem/1904
포인트 쳌쳌
- 이 문제는 간단히
a[n] = a[n-1] + a[n-2]
라는 점화식으로 표현할 수 있다. 즉, 피보나치 수열을 이용하는 문제이다. - 문제에서 결과를 15746으로 나눈 나머지를 출력하라고 했고 이것은 n의 값에 따라 굉장히 많은 메모리를 소모하기 때문에(
오버플로우
) 사용한 방법이다.
풀이 코드
처음 생각한 풀이 방식
사실 나는 입력값에 대한 결과숫자가 얼마나 클지 예상을 못하고 재귀함수를 이용하여 풀이를 했었다. 먼저, tile이란 리스트를 만들어 문자열 ‘00’과 ‘1’을 넣어두고 재귀 깊이에 따라 n이라는 문자열 길이가 될 때까지 만들었다.
문자열의 길이가 n이 되면 결과값들을 의미하는 result 리스트에 저장했고, 결과에서는 이 result의 개수를 출력하도록 했다.
하지만 이 코드는 런타임에러가 난다..!
import sys
n = int(input())
tile = ['00', '1']
result = []
def counting(ans, idx):
ans += tile[idx]
if len(ans) >= n:
if len(ans) == n:
result.append(ans)
return
if idx == 1:
idx = 0
counting(ans, idx+1)
counting(ans, idx)
counting('', 0)
counting('',1)
#print(result)
print(len(result) % 15746)
오늘도 구신의 도움으로 이 문제는 재귀알고리즘으로 풀면 안된다 는 것을 깨달았다.
문제의 핵심
문제를 직관적으로 푸는 것이 아니라 그 안에 담긴 의미를 간략하게 풀어내어 코드로 나타내는 것 이 관건인 것 같다. 또한 15746진법을 이용하는 이유는 무수히 큰 숫자의 앞부분을 잘라내줌으로써 오버플로우를 방지한다 는 것이다.
‘15746’로 나누는 이유가 잘 이해가 가질 않는다면 백준 질문게시판 중 이 글에 달린 댓글을 참고하면 좋을 것 같다!
다음은 피보나치 수열 풀이와 거의 동일한 이 문제의 정답 코드이다.
메모이제이션을 이용한 풀이이다.
#정답코드
n = int(input())
fibo = [0]*1000001
fibo[1] = 1
fibo[2] = 2
for i in range(3, n+1):
fibo[i] = (fibo[i-1]+fibo[i-2])%15746
print(fibo[n])
참고자료
이번 문제를 해결하는데 도움을 받은 포스팅. 정리를 정말 잘 해주신 것 같다!
https://sungmin-joo.tistory.com/21?category=851625