[백준] (Swift) 15990번 - 1,2,3 더하기 5 (DP 기초 문제, 2차원 배열 사용하여 동적계획법 문제 풀기)

 

문제 링크

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

15990번: 1, 2, 3 더하기 5

 

풀이 IDEA

(DP 어렵다 .. 나중에 코딩테스트 문제를 연습할때 dp 부분을 집중적으로 공략할 것이다 ㅠㅠ )

먼저 풀었던 "백준 9095번 1,2,3 더하기" 와는 다르게, 더해지는 숫자의 "순서!!"를 생각해야한다는 점이 어려웠다. 

9095번	4를 만들기 위한 경우의 수	1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 같은 수 중복 가능
15990번 (지금 문제)	4를 만들기 위한 경우의 수	1+2+1 1+3 3+1 같은 수 연속 금지!

9095번의 점화식을 보면 dp[n] = dp[n-1] + dp[n-2] + dp[n-3] 로, 그저 중복이 가능했기 때문에 일정한 규칙을 찾아서 문제의 답을 쉽게 구할 수 있었다.  하지만 지금 풀 문제인 15990을 보면, 같은 수가 연속해서 등장하지 않아야 한다는 조건이 붙어있다. 이를 어떻게 해결하면 좋을까?

우선, 앞에서 dp 문제를 풀면서, dp 배열에는 '경우의 수'를 value 로 넣는것으로 약속했다. 그럼, 어떻게 하면 바로 이전의 경우의 수로부터 어떤 방식으로 경우의수가 늘겠는가?를 생각해보면, 아래와 같이 생각할 수 있다.

• 맨 뒤의 숫자가 [1] 인 경우, [2] 나 [3] 을 더할 수 있다.
• 맨 뒤의 숫자가 [2] 인 경우, [1] 이나 [3] 을 더해줄 수 있다.
• 맨 뒤의 숫자가 [3] 인 경우, [1] 이나 [2] 를 더해줄 수 있다. 

이렇게 세가지로 나누어서 생각해볼 수 있다. 이 세가지를 2차원 배열로 표현할 거다. dp[i][1], dp[i][2], dp[i][3] 으로 해서 1로끝나는 경우의 수 를 dp[i][1] 에, 2로 끝나는 경우의 수를 dp[i][2] 에 말이다.

그럼 더 쉬운 이해를 위해서 숫자 6을 기준으로 생각해보자. 우선, 우리는 1,2,3을 가지고 계산을 한다. 더할 수 있는 수에서 3이 최고 숫자이기 때문에, 우리는 3을 만드는 경우의 수부터 따지면 된다.

5를 만들 수 있는 경우의 수  (1을 더해주어야 6이 된다!)	2+1+2 1+3+1 2+3 3+2 (4가지)	1로 끝나는 경우 1+3+1+1 1로 끝나는 경우는 생각할 수 없다. 왜냐면 +1을 해주면 연속이 발생하기 때문이다. 2로 끝나는 경우 2+1+2+1 3+2+1 3으로 끝나는 경우 2+3 +1	여기서 dp[5]에서 가져온 4가지의 경우의 수는, 모두 dp[6] 에서 [1]로 끝나는 경우의 수가 되고, dp[6][1] = 3이 된다!
4를 만들 수 있는 경우의 수 (2를 더해주어야 6이 된다)	1+2+1 1+3 3+1 (3가지)	1로 끝나는 경우 1+2+1+2 3+1 +2 2로 끝나는 경우 x 2로 끝나는 경우는 생각할 수 없다. 왜냐면 +2 를 해주면, 연속이 발생하기 때문이다. 마침 해당 경우에는 2로 끝나는 경우가 없긴하다. 3으로 끝나는 경우 1+3 + 2	여기 dp[4] 로 부터 가져온 3가지의 경우는, 모두 dp[6]에서는 [2]로 끝나는 경우의 수가 된다. 즉, dp[6][2]=3 이 된다!
3을 만들 수 있는 경우의 수 (3을 더해주어야 6이 된다)	1+2 2+1 3	1로 끝나는 경우 2+1+3 2로 끝나는 경우 1+2+3 3으로 끝나는 경우 3 +3 3으로 끝나는 경우는 생각할 수 없다. 왜냐면 +3을 해줄 것이기 때문이다.	마찬가지로, dp[6][3] = 2 가 된다.

위를 도식화 해보자.

• dp[6-1][1] = dp[6-1][2] + dp[6-1][3]     (1로 끝나는 경우 = 2로 끝나는 경우 + 3으로 끝나는 경우)
• dp[6-2][2] = dp[6-2][1] + dp[6-2][3]   (2로 끝나는 경우 = 1로 끝나는 경우 + 3으로 끝나는 경우)
• dp[6-3][3] = dp[6-3][1] + dp[6-3][2]   (3으로 끝나는 경우 = 1로 끝나는 경우 + 2로 끝나는 경우)

이 규칙을 소스코드로 구현하면 아래와 같다.

 

소스코드

https://github.com/deslog/Algorithm/blob/main/Algorithm/Boj/15990_1%2C2%2C3%20%EB%8D%94%ED%95%98%EA%B8%B0%205/main.swift

GitHub - deslog/Algorithm

 

배열은 0부터 생성되기 때문에 쉽게 생각할 수 잇게 모두 +1 하여 배열을 생성해주었다. 

let n = Int(readLine()!)!
var dp = [[Int]](repeating: Array(repeating: 0, count: 4), count: 100001)

dp[1] = [0, 1, 0, 0]
dp[2] = [0, 0, 1, 0]
dp[3] = [0, 1, 1, 1]

for j in 4..<100001 {
    dp[j][1] = dp[j-1][2]%1000000009 + dp[j-1][3]%1000000009
    dp[j][2] = dp[j-2][1]%1000000009 + dp[j-2][3]%1000000009
    dp[j][3] = dp[j-3][1]%1000000009 + dp[j-3][2]%1000000009
}


for _ in 1..<n+1 {
    let i = Int(readLine()!)!
    print((dp[i][1]+dp[i][2]+dp[i][3])%1000000009)
}

 

여기서 잠깐, 왜 print 하기 이전에 100001 개의 배열 모두 생성해 두고 시작하는지 궁금할 수 있다. 그래서 나는 for문을 이용해서 입력되는 숫자만큼만 배열을 생성하게 만들었다. 그러면 문제가 생기는게, dp[50]를 구하고, dp[100]을 구할때, 또 똑같은 연산을 반복하기 때문에 연산량이 +N 씩 더 들기 때문에 초반에 100001 길이의 배열을 모두 생성해 둔 상태에서 출력하는 것이 더 빨랐던것이다.