[DP]1, 2, 3더하기4

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다.

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

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

입력

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

출력

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

예제 입력 1 복사

3
4
7
10

예제 출력 1 복사

4
8
14

풀이방법

• dfs
• DP

처음엔 dfs로 1,2,3을 더할 때의 경우의 수를 재귀를 통해 돌면서 result값을 늘려가는식으로 문제를 풀었었다. 그러나 시간초과.. ㅠ

대부분 dfs에서 시간초과가 나오는 문제들은 DP 방법으로 풀면 시간초과부분이 해결이 됬기에 DP 방법으로 문제를 접근해봤다.

규칙 찾기

DP문제의 핵심은 점화식을 만드는 것이기 때문에 규칙을 찾기위해 8까지 직접 적어봤었다..

1 - 0
2
1+1

3 = 3
1+1+1
2+1
3

4 ~ 3 + 1 = 4
1+1+1+1
2+1+1
2+2
3+1

5 
1+1+1+1+1

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

3+1+1


6
1+1+1+1+1+1

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

3+1+1+1
3+3

7
1+1+1+1+1+1+1

2+1..
2+2+1+1+1
2+2+2+1
2+2+3
2+3+1+1

3+1+1+1+1
3+3+1


3+3+1

8
1+1+1+1+1+1+1+1

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

3+1..
3+3+1+1

그리고 보인것:

• 맨 앞 부분인 1로만 더하는 경우의 수는 1밖에 없고
• 2로 시작하는부분 다음에 나오는합은 2 이전의 경우의 수와 똑같다는것
• 하지만 3의 경우를 2와 똑같이 적용하면 2의 부분과 3의 부분에 중복의 값이 생기기 때문에 중복을 제외했을 경우 3 이후 1로만 더하거나 3을 최대한 더한 후 나머지값을 1로 채우는 경우의수로 나뉜다는것

을 발견했다.

예를 들어서 6의 경우는

• 1+1+1+1+1+1 -> 무조건 1개

• 2로 시작하는부분은 2+ [4의 경우의 수]

2+ 1+1+1+1

2+2+1+1

2+2

이렇게 된다

• 3의 경우의 수는 3 다음 1로만 가득한경우 1과 3을 채울 수 있는 경우의 수의 합이다.

3+1+1

// 만약 6이었다면 3+3 의 경우의수가 추가됬을 것이다.

그래서 나온 점화식은..

dp[i] = 1+dp[i-2]+i/3

이다.

풀이

import Foundation

let count = Int(readLine()!)!

for _ in 0 ..< count {
    let n = Int(readLine()!)!
    var dp: [Int] = Array(repeating: 0, count: n + 1)
    if n < 5 {
        if n == 1 {
            print(1)
        } else if n == 2 {
            print(2)
        } else if n == 3 {
            print(3)
        } else if n == 4 {
            print(4)
        }
    } else {
        dp[2] = 1
        dp[3] = 3
        dp[4] = 4
        dp[5] = 5
        for i in 5...n {
          // 점화식
            dp[i] = 1 + dp[i-2] + i/3
        }
        print(dp[n])
    }
}

의문점

이 문제는 잘못됬다. 처음에 이문제를 계속 틀렸었는데 이유가 dp[1] = 0으로 했기 때문이다. dp[1]은 1,2,3의 합으로 표현할 수 있는 경우의 수임으로 1은 플러스가 안들어 가기 때문에(1+0 의 경우도 1,2,3이 아니기 때문에 안된다.) 0이라고 생각했는데 이것도 경우의수로 쳐주니깐 정답이 됬다.

오류 수정을 추가할려고했지만 현재는 오류수정을 안받는다고 한다..