[백준 9095 파이썬] 1,2,3 더하기

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

9095번: 1, 2, 3 더하기

 

이 문제는 DP 문제이다. 

DP를 풀려면 어떤 패턴이나 규칙을 찾아야 하는데.... 뭔가 알듯 말듯 싶어서 

일일히 다 계산을 나열을 해보면서 규칙을 찾아보았다.

처음에 F(1),F(2),F(3)까지는 일정한 규칙이 없었지만 F(4)부터 

F(N)=F(N-1)+F(N-2)+F(N-3) 점화식을 세울 수 있었다.

 

1개          F(1)=(1)                                     

2개          F(2)=(1+1),(2)

4개          F(3)=(1+1+1),(2+1),(1+2),(3)

 

7개          F(4)= F(1)+3, F(2)+2, F(3)+1 를 더한 리스트와 같다.

                         (1+3) (1+1+2),(2+2)  (1+1+1+1),(2+1+1),(1+2+1),(3+1)

 

 

 

Bottom-up 방식

# 입력값을 받습니다.
T = int(input()) # 테스트 케이스의 개수

# 다이나믹 프로그래밍을 위한 초기값을 설정합니다.
dp = [0] * 11
dp[1] = 1 # 1을 만드는 방법은 1 하나뿐입니다.
dp[2] = 2 # 2를 만드는 방법은 1+1, 2 두 가지입니다.
dp[3] = 4 # 3을 만드는 방법은 1+1+1, 1+2, 2+1, 3 네 가지입니다.

# Bottom-up 방식으로 다이나믹 프로그래밍을 수행합니다.
for i in range(4, 11):
    dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

# 각 테스트 케이스에 대하여 정답을 출력합니다.
for _ in range(T):
    n = int(input()) # 만들어야 하는 수
    print(dp[n]