[백준9095번][백준][baekjoon][9095번][1,2,3더하기][DynamicProgramming][DP][Python][파이썬]

문제링크

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

9095번: 1, 2, 3 더하기

문제

 

풀이

DP로 풀면 효과적으로 풀 수 있는 문제입니다. 정수 4를 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제입니다. 제한 조건으로, 합을 나타낼 때는 수를 1개 이상으로 사용해야 한다는 것을 염두하셔야 합니다. (DP 유형 및 다른 유형의 알고리즘에서와 같이 분할 문제로 해결하는 것을 방지). 이 문제는 표현하는 수가 1, 2, 3 으로 세 가지밖에 안되어 그리 어렵지 않게 풀 수 있는 문제입니다. 먼저 경우의 수를 나열해 보겠습니다.

 

정수 1을 숫자로 표현하는 방법(1) [ 1 ]

정수 2를 숫자로 표현하는 방법(2) [ 1+1 ], [ 2 ]         

정수 3을 숫자로 표현하는 방법(4) [ 1+1+1 ], [ 2+1 ], [ 1+2 ], [ 3 ]

정수 4를 숫자로 표현하는 방법(7) [ 1+3 ],

                                            [ 1+1+2 ], [ 2+2 ],

                                            [ 1+1+1+1 ], [ 2+1+1 ], [ 1+2+1 ], [ 3+1 ]

정수 5를 숫자로 표현하는 방법(13)  [ 1+1+3 ], [ 2+3 ],

                                              [ 1+1+1+2 ], [ 2+1+2 ], [ 1+2+2 ], [ 3+2 ],

                                              [ 1+3+1 ],

                                              [ 1+1+2+1 ], [ 2+2+1 ],

                                              [ 1+1+1+1+1 ], [ 2+1+1+1 ], [ 1+2+1+1 ], [ 3+1+1 ] 

 

괄호 한에 있는 숫자는 숫자를 표현하는 방법의 수 입니다. DP문제를 풀기 위해서는 점화식을 세워야 하는데 위의 경우의 수를 보면 어느 정도 느낌이 올 겁니다. 정수 N을 표현하기 위해서는 N-3을 표현하기 위한 방법에 3을 추가, N-2를 표현하기 위한 방법에 2를 추가, N-1을 표현하기 위한 방법에 1을 추가하면 정수 N을 표현하기 위한 방법의 경우의 수가 나옵니다. 이를 점화식으로 나타내면 아래와 같습니다.

 

D[N] = D[N-3] + D[N-2] + D[N-1]

 

위의 과정을 반복하면 정수 N을 표현하기 위한 방법의 경우의 수를 구할 수 있습니다.

코드

#Python

testcase=int(input())
 
dp=[ 0 for i in range(12)]
 
dp[1]=1
dp[2]=2
dp[3]=4
 
for i in range(4,12):
    dp[i]=dp[i-1]+dp[i-2]+dp[i-3]
 
for i in range(testcase):
    a=int(input())
    print(dp[a])

오류 또는 더 좋은 풀이 방법이 있다면 댓글로 남겨주세요.

이번 포스팅에서는 python으로 작성하였지만, 추후 C와 C++ 코드도 올리도록 하겠습니다.