[DP] 백준 1904. 01타일

 

 풀이 과정 

 

 

1. 점화식으로 표현해보기 

2. 작은 수부터 일일이 계산해 규칙 찾아내기

3. 바텀업으로 풀어보기                         >>> 런타임 에러

4. 생략된 규칙 추가하기 (%15746)      >>> 메모리 초과

5. %15746의 위치를 출력 구문이 아닌, 입력 부분으로 옮김  >>> 런타임 에러

 

 

 

 

------  계속해서 index 에러가 나고 있었다. 다른 분들의 코드를 참고한 결과, 가장 큰 차이점은 빈 배열을 만드는 부분이었따.

나는 d = [0] * (n+1)로 했는데, 다른 사람들은 아예 배열의 길이를 N의 최대값인 1000000+1로 고정해뒀더라.

그걸 수정하니, 정답처리 되었다. 아직 왜 그런지는 모르겠다.

import sys
input = sys.stdin.readline

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

print(d[n])