[Swift][DP] 백준 15990번 (1, 2, 3 더하기 5)

요구능력 : DP의 개념을 알고 규칙을 찾을 수 있느냐

 

코드설명 : 

 

맨 오른쪽 수를 기준으로 규칙이 나온다.

1, 2, 3으로만 더하라고 했고, 중복된 수가 없어야한다고 했다.

 

수가 n이라고 가정하면,

f(n)

(n - 1) + 1

(n - 2) + 2

(n - 3) + 3 이 있다.

 

위 그림과 같이 f(5)까지 있다고 가정하면 아래와 같은 규칙이 나온다.

f(5)의 4 + 1에서 4는 f(4)에 있는 2 + 2와 1 + 3으로 대체된다.

배열을 보면

dp[i][1]

dp[i][2]

dp[i][3] 이 있다.

 

dp[i][1]은 수의 마지막자리가 1인 수의 개수를 저장

dp[i][2]은 수의 마지막자리가 2인 수의 개수를 저장

dp[i][3]은 수의 마지막자리가 3인 수의 개수를 저장

 

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

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

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

식이 성립한다.

 

마지막자리가 똑같으면 중복되기 때문에 중복을 피하기 위함이다.

 

잘 이해가 가지않으면 위의 사진을 보고 f(5)에 2+2+1 이 되지않냐고 할 수 있다.

하지만 이는, 2+1+2가 될 수 있다.

그럼, f(4)의 [1]도 되는거 아닌가?

아니다, 이미 아래에 1 + 3이 있어서 굳이 그럴필요가 없다.

 

이거까지 다 고려해서 찾아진 규칙이다.

 

결국 f(5)는 5가 된다.

 

후기 :  이건 규칙찾기가 어마어마하게 어렵다. 이걸 바로 푼 사람들은 괴물인건가..

let T = Int(readLine()!)!
var dp = Array(repeating: Array(repeating: 0, count: 4), count: 100001)
dp[1][1] = 1
dp[2][2] = 1
dp[3][1] = 1
dp[3][2] = 1
dp[3][3] = 1

for i in stride(from: 4, through: 100000, by: 1) {
    dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % 1000000009
    dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % 1000000009
    dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % 1000000009
}

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