DP(1, 2, 3 더하기 3/S2) - 15988

1. 문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

 

2. 입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 1,000,000보다 작거나 같다.

3
4
7
10

 

3. 출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

7
44
274

 

4. 코드

import sys

input = sys.stdin.readline
t = int(input())
# 초기값
nums = [1,1,2]

for _ in range(t):
  n = int(input())
  
  for m in range(len(nums)-1,n+1):
    # 점화식 n = (n-3) + (n-2) + (n-1)
    nums.append((nums[-3]+nums[-2]+nums[-1] )%1000000009)
  # 결과값 출력
  print(nums[n])

 

5. 풀이설명

① 입력값 t를 입력받는다.

 

② nums 배열의 초기값을 1,1,2로 생성한다.

 

③ t만큼 반복문을 실행하여 n을 입력 받는다.

 

④ nums 배열의 길이 인덱스 부터 n+1 까지 반복문 실행한다.

 

⑤ nums 배열에 (nums[-3]+nums[-2]+nums[-1])%1000000009을 추가한다.

 

⑥ 점화식 반복문이 끝나면 nums[n]을 결과값으로 출력한다.

 

 

6. 느낀점

점화식 n = (n-3) + (n-2) + (n-1)을 구하여 풀었다. 초반에는 nums 배열을 2차원까지 생성해서 메모리초과가 나오고 두번째는 점화식 계산 반복문 돌릴 때 nums 배열 for 문을 0부터 돌려서 시간 초과가 나왔다 len(nums) 부터 돌리면 결과값이 정상적으로 출력된다.