🔔 문제 설명은 백준 문제 링크로 대신합니다
피보나치 수열이라 메모이제이션 방식과 바텀업 방식 둘 다로 풀어보았는데, 메모이제이션 방식은 재귀 깊이 설정(setrecursionlimit())을 안 하거나 충분한 깊이로 하지 않으면 RecursionError가 발생하고, 충분한 깊이로 하면 메모리 초과가 발생한다. 문제에서 N의 범위가 1 ≤ N ≤ 1,000,000 라고 해서 재귀 깊이를 10**7로 했더니 메모리가 초과되고, 줄였더니 런타임에러가 발생했다. 결국 메모이제이션 방식 대신 바텀업 방식으로 통과했다.
이 문제에서 가장 어려운 부분은 이게 피보나치 수열이라는 것을 알아내는 것이었다.
N=1 일 때는 1 - 1개
N=2 일 때는 00, 11 - 2개
N=3 일 때는 100, 001, 111 - 3개
N=4 일 때는 0000, 1100, 1001, 0011, 1111 - 5개
N=5일 때는 10000, 00100, 11111, 00001, 10011, 00111, 11111 - 8개
분명히 뭔가 규칙이 있을텐데, 하면서 30분동안 요리보고 저리보았더니 한 가지 패턴이 보였다.
N=3일 때의 결과는 N=1일 때의 결과의 뒤에 00을 붙이고, N=2일 때의 결과의 뒤에 1을 붙인 것이었다.
유사하게 N=4일 때의 결과는 N=2일 때의 결과의 뒤에 00을 붙이고, N=3일 때의 결과의 뒤에 1을 붙인 것이었다.
즉, N번째 결과는 N-2의 결과에 00을 더한 것과 N-2의 결과에 1을 더한 것이고, 그 갯수는 1,2로 시작하는 피보나치 수열이다!
피보나치 수열이라는 것을 깨달은 이후부터는 상향식 접근 방식으로 문제를 풀 수 있었다. (상향식 접근 방식에 대한 좀 더 자세한 설명은 백준 피보나치 수2 풀이에 기록 ) 문제에서 N번째 수를 15746로 나눈 나머지를 출력하라기에 처음부터 나눠주면서 계산해나갔다. (처음부터 나눠도 결과는 같으나 수가 더 작기에 속도가 더 빠르다)
N = int(input())
if N ==1 :
print(1)
else :
a= 1
b= 2
for i in range(2, N) :
temp = a
a= b
b = (temp+a)%15746
print(b)
처음에 저 N==1 일때 print(1)하는 부분을 빼먹었더니 채점이 100%에서 틀렸습니다! 가 나왔다. ㅎ 언제쯤 이런 것좀 안 빼먹을 수 있으려나 ㅎㅎㅎㅎ
메모리초과가 났지만 메모이제이션 방식으로 푼 코드도 함께 올려논다. (아니 여기선 n이 1 or 2일 때 처리 잘 해줬으면서 왜 바텀업 코드에서는 홀랑 까먹은 것일까!!!)
import sys
sys.setrecursionlimit(10**7)
N = int(input())
def tile(n, memoization={}):
if n ==1 or n ==2
return n
if not memoization.get(n) :
memoization[n] = (tile(n-2)+tile(n-1))%15746
return memoization[n]
print(tile(N))
한줄소감: 문제 풀이 시간으로 잡아놓은 30분 제한이 끝나갈 때까지 피보나치가 너무 안 보여서 포기할까 싶을 때쯤! 피보나치 수열이 눈에 들어왔다. 기뻤다!!!!!
끝.
'TIL' 카테고리의 다른 글
백준 11049. (PyPy3 1등 먹은 풀이!) 행렬체인곱셈 | Python 다이나믹 프로그래밍 (0) | 2022.10.19 |
---|---|
백준 11047. 동전 0 | Python | 그리디 (0) | 2022.10.15 |
백준 2748. 피보나치 수 2 | Python | 메모이제이션 & 바텀엄(상향식) 접근 방식 풀이 (0) | 2022.10.14 |
[정글 TIL] 유클리드 호제법 , 재귀 알고리즘 (1) | 2022.09.26 |
[정글 TIL] Week01 | 입출력, 산술연산자(/,//,%) (0) | 2022.09.26 |
댓글