[알고리즘/동적 계획법] 9095번 : 1, 2, 3 더하기 - python

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

9095번: 1, 2, 3 더하기

---

• 문제
• 소요시간 :

---

• 설계하기(접근방법) 

1. 테스트 케이스를 입력받고, dp[]를 선언한다

2. 알고리즘해석

1) 정수 3을 생각해보자

3은  3, 2+1,1+2, 1+1+1로 나눌 수 있다

2) 정수 2를 생각해보자

2는 2, 1+1로 나눌 수 있다.

3) 정수 1을 생각해보자

1은 1로 나타낼 수 있다.

 

4) 정수 4를 생각해보자

5) 정수 5를 생각해보자

1+1+1+1+1

1,1,1,2 * 4 경우

1,2,2 * 3 경우

1,1,3 * 3 경우

2,3 * 2 경우

 

dp[1] = 1

dp[2] = 2

dp[3] = 4

dp[4] = 7

dp[5] = 13

 

규칙에서 dp[n] = dp[n-1] + dp[n-2] + dp[n-3] 인것을 알 수 있다.

하지만 왜 이런 규칙이 나왔는지 처음 풀이에서 알지 못했다

 

다른 사람의 풀이를 참고하여 그 이유를 알게 되었다.

 

3이 최대 수의 한계이니 다음과 같은 방법이 형성된다

dp[4]를 예시로

dp[4] = (dp[3] + 1. dp[2] + 2, dp[1] + 3)의 집합이다.

 

dp[1] = 1

dp[2] = 1 + 1

            2

dp[3] = 1 + 1 + 1

            1 + 2

            2 + 1

            3

 

인데

dp[1] = 1 + 3

dp[2] = 1 + 1 + 2

            2 + 2

dp[3] = 1 + 1 + 1 + 1

            1 + 2 + 1

            2 + 1 + 1

            3 + 1

의 형태가 된다고 할 수 있다. 각 마지막 자리에 더해지는 수(1,2,3) 도 다르니 순서로 인한 중복을 신경쓰지 않아도 된다.

따라서

dp[n] = dp[n-1] + dp[n-2] + dp[n-3]와 같은 점화식이 나오는 것을 알 수 있다.

 

 

---

• 코드(출력)

t = int(input())

dp = [0] * 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(t):
    n = int(input())
    print(dp[n])

---

• 얻어갈 부분

1. 동적 프로그래밍이 정말 풀리지 않을 때에는 일단 숫자를 나열해서 규칙을 찾아보자

2. 문제가 풀리지 않을 때에는 식을 펼쳐서 경우의 수를 하나하나 확인해보자