백준 15988 - 1, 2, 3 더하기 3 (Python)

문제

https://www.acmicpc.net/problem/15988

15988번: 1, 2, 3 더하기 3

 

풀이

a = [int(input()) for i in range(int(input()))]
target = max(a)
save = [1] * (target + 1)
save[1] = 1
save[2] = 2
save[3] = 4
for i in range(4,target+1):
    save[i] = (save[i-1] + save[i-2] + save[i-3])%1000000009

for i in a:
    print(save[i]%1000000009)

 

이전에 풀었던 9095번 1, 2, 3 더하기 문제와 비슷한 문제이다.

해당 문제의 풀이는 아래 링크 참고

2024.02.12 - 백준 9095 - 1, 2, 3 더하기 (Python)

백준 9095 - 1, 2, 3 더하기 (Python)

 

9095번과 다른점은 n의 범위가 1,000,000 이하라서 숫자가 엄청나게 커진다는 점이다. 처음에는 결과에 1,000,000,009 나누어 출력하는 코드만 추가하여 제출하였는데 메모리 초과가 났다.

 

따라서 배열에 저장해줄때도 나머지 연산을 해서 저장을 해주니 정답입니다를 받을 수 있었다.

 

나눈 값을 저장해두어도 최종 결과가 옳게 나오는 것을 알 수 있는데 이는 모듈러 연산의 성질을 통해 증명할 수 있다.

수학쪽은 부족한 점이 많아서 조금 더 공부하고 글을 써야될 것 같아서

지금은 (a+b)%c = {(a%c)+(b%c)}%c 라는 것만 알고 넘어갔다.

 

아 그리고 1, 2, 3 더하기 2 문제도 있던데 곧 풀어서 올릴 예정이다.