[백준] 9095번 : 1, 2, 3 더하기 (Python)

문제 : https://www.acmicpc.net/problem/9095

 

 

이 문제는 숫자 N을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제다.

 

import sys

input = sys.stdin.readline

T = int(input()) # 테스트 케이스의 개수

answer = [0]*(11) # 정답 리스트
answer[:4] = [0, 1, 2, 4] # 초기 정답 저장

# 정답 리스트 생성
for i in range(4, 11):
    answer[i] = answer[i-1]+answer[i-2]+answer[i-3] # 다음 정답을 생성해 저장

# 정답 구
for N in range(T):
    N = int(input()) # 값을 구할 N 입력받기
    print(answer[N]) # 0과 1의 개수 print

 

 

[문제풀이]

---

 

이 문제를 풀기 위해선 우선 규칙을 찾아야 한다.

 

숫자 N의 경우의 수는 n-1, n-2, n-3의 경우의 수의 합이란 것을 알 수 있다.

 

arr[i] = arr[i-1] + arr[i-2] + arr[i-3]

 

이를 점화식으로 만들면 이렇게 되며, 이를 코드로 구현하기만 하면 끝난다.