[Swift][DP] 백준 2225번 (합분해)

요구능력 : DP에 대한 이해

 

코드설명 : 

이해가 정말 잘되게 해주신 블로그

 

우선 구해야되는 배열의 개수가 얼마안되서 그냥 처음부터 끝까지 다 구해버리고 거기서 해당되는 배열[k][n]을 뽑아냈다.

위에 태그해놓은 블로그를 먼저 보고오면 어떤식으로 풀어야할지 감이 잡힌다.

 

2차원배열인걸 처음에 어떻게 알고 풀지라고 생각했는데,,

DP는 입력이 2개가 반드시 들어와서 찾는거라면 2차원이 아닐까.. 라는 생각을 조심스럽게 해본다.

 

여튼 이제 2차원으로 푸는건 위에 블로그에서 설명해주신대로 표그려서 풀어야겠다..

 

후기 : 어려운거 같은데,, 알고나면 이렇게 푸는방법도 있구나 싶은 문제였다.

많은 정보중에서 내가 이 문제를 다시 봤을 때 논리적으로 풀 수 있겠다 싶은 방법으로 풀었다.

let nk = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nk[0]
let k = nk[1]
var dp = Array(repeating: Array(repeating: 0, count: 201), count: 201)

for i in 0...200 {
    dp[i][0] = 1
}

for i in stride(from: 1, through: 200, by: 1) {
    for j in 1...200 {
        dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000000
    }
}

print(dp[k][n])