[백준/Swift] 11057번: 오르막 수

 

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

11057번: 오르막 수

 

길이가 N인 오르막수의 개수를 구하는 문제

-> 길이가 1~N인 오르막수의 개수를 모두 구해보자.

표를 만들어서 해보면

큼큼 굉장히 지저분하지만, 딱 알 수 있다.

 

dp의 행 i는 1~N까지의 길이, 열은 j로 끝나는 수를 말한다. 즉, dp[i][j]는 i길이의 오르막 수 중에서 j로 끝나는 수의 개수

여기서 관건은 사실 i, j를 선언하는 것이다. j를 개념 정의를 할 수 없다면.. 이렇게 풀 수도 없겠지.

DP에서는 점화식을 만들기 위해 공통된 부분을 찾아야 하는데, (j 개념) 이 부분이 어렵다ㅠ

그래서 왠만하면 예시를 하나 두고 쭉 그려보면 좋다.

 

위에서 빨간 부분으로 보이는데, 이 표를 통해 점화식을 알아낸 것이다.

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

 

import Foundation

//input
let n = Int(readLine()!)!
var dp = [[Int]](repeating: [Int](repeating: 0, count: 11), count: n+1) //오르막수 개수

//initial
dp[0][0] = 0
for i in 0..<10 {
    dp[1][i] = 1
}
for i in 0...n {
    dp[i][0] = 1
}
if n == 1 {
    print(10)
}else {
    for i in 2...n {
        for j in 1..<10 {
            dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % 10007
        }
    }
    print(dp[n].reduce(0, +) % 10007)
}

 

 

이것두 DP 문제

개념 잡기 위해 사실 공부하면서 하는 거라 이게 문제만 딱 나왔을 때 제대로 풀 수 있을지 모르겠다.

그러니까 많이 풀어봐야지!! 화이팅이다~~