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

요구능력 : DP점화식

 

코드설명 : 

 

기존의 1,2,3더하기와 비슷한데  "합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다."라는 조건이 붙었다.

1,2,3더하기 문제는 특징이 있는데 1과 2와 3을 기준점으로 세우고 해당하는 수가나오도록 더하는것이다.

예를들어서 4가있으면

3 + 1

2 + 2

1 + 3

이런식으로 기준을 1,2,3으로 두고 문제를 풀면된다.

 

중복된 수의 순서가 안나오려면 1,2,3을 기준으로 두고 뒤에 나오는수가 작거나같으면된다.

예를들어 4가있으면

1뒤에는 1보다 작거나 같은 수가 나와야한다.

1 + 1 + 1 + 1

2뒤에는 2보다 작거나 같은 수가 나와야한다.

2 + 2, 2 + 1 + 1

3뒤에는 3보다 작거나 같은 수가 나와야한다.

3 + 1

이렇게 4가지 나오게된다.

 

점화식을 구할때는 맨앞의 1, 2, 3을 기준으로 구하면된다.

수가 i일때 맨 앞수가 1이면 뒤에는 i - 1에 해당하는 수가 나와야한다.

그리고 작거나 같은 수만 나와야한다.

그렇기 때문에 i - 1에서도 1로 시작하는 갯수를 갖고와야한다.

 

점화식은 아래와 같다.

dp[i][1] = dp[i - 1][1]

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

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

 

후기 :  1, 2, 3더하기는 문제를 어떻게 이렇게 내는건지 참 신기한거같다.

한가지 주제로 여러가지로 잘꼬아서낸다.

let t = Int(String(readLine()!))!
var dp = Array(repeating: Array(repeating: 0, count: 3), count: 10001)
dp[1][0] = 1
dp[2][0] = 1
dp[2][1] = 1
dp[3][0] = 1
dp[3][1] = 1
dp[3][2] = 1
for i in stride(from: 4, to: 10001, by: 1){
    dp[i][0] = dp[i - 1][0]
    dp[i][1] = dp[i - 2][1] + dp[i - 2][0]
    dp[i][2] = dp[i - 3][0] + dp[i - 3][1] + dp[i - 3][2]
}
for _ in 0..<t{
    let a = Int(String(readLine()!))!
    print(dp[a][0] + dp[a][1] + dp[a][2])
}