[Swift][DP] 백준 11057번 (오르막 수)

요구능력 : DP에 대한 이해

 

코드설명 : 

 

수의 길이에 따른 오르막 수의 개수를 세는 문제이다.

오르막수는 오름차순과 비슷한데 같은 수가나와도 오르막수가 된다.

예를들면 1 2 3, 1 2 2은 오르막 수 인데,

1 2 1, 1 2 0은 오르막수가 아니다.

 

이 문제에서 주의깊게 봐야할 점은 004 이런것도 다 세줘야하는것이다.

수는 0으로 시작할 수 있다는게 이런의미.

 

수를 관리하기위한 문제는 2차원 배열을 생각하는게 좋다.

수의 끝을 기준으로 DP구하기가 수월하기 때문이다.

 

DP[1][0]은 1자리수에 끝자리 수가 0으로 끝나는것이다.

DP[3][5]는 3자리수에 끝자리 수가 5로 끝나는 것이다.

 

DP[1][0]부터 DP[1][9]까지는 1을 삽입해준다.

DP[1][0]은 1자리에 끝이 0으로 끝나는것인데 개수는 1개이다. 나머지도 마찬가지이다.

 

그럼 DP[2][0]을 보자.

두자리수에 끝이 0으로 끝나는 것을 말한다.

문제의 규칙은 오르막수이기 때문에 0으로 끝나는것 앞에는 0밖에 나올 수 없다.

따라서 DP[2][0] = DP[1][0] 밖에 올 수 없는 것이다.

 

다음으로 DP[2][1]을 보자.

두자리수에 끝이 1로 끝나는 것을 말한다.

규칙대로 DP[2][1] = DP[1][0] + DP[1][1] 이 된다.

 

?1 이라고 치면 ?에는 1보다 작거나 같은 수 들이 들어올수 있는것이다.

현재 자리수는 두 자리이고 끝자리가 1로 정해져있어서 앞에는 1개의 숫자만 오면된다.

올 수 있는 수가 0과 1인것인데 우리가 필요한것은 1자리이기 때문에 DP[1][0] + DP[1][1]의 수만큼 필요한 것이다.

 

만약 DP[3][5]가 있다고 한다면,

DP[3][5] = DP[2][0]+ DP[2][1] + DP[2][2]+ DP[2][3] + DP[2][4] + DP[2][5] 가 되는것이다.

DP[2][0] ~ DP[2][9]는 이미 앞전에 구해져있기 때문에 사용할 수 있는것이다.

이것도 마찬가지로 3자리수에서 맨끝자리수가 5인데 앞에는 5보다 작거나같은 2자리수가 들어오는 것이라서 위처럼 하는 것이다.

참고로, 출력할 때는 0~9로 끝나는 자리수의 수를 모두 세야하므로 for문으로 마무리해줬다.

 

후기 : 이렇게 숫자 차순으로 장난치는 문제는 숫자 자릿수에 따른 맨 끝의 수를 생각해서 풀어야겠다.

숫자 DP는 거의 다 끝의 수가 중요한거같다. 1,2,3더하기 문제도 마찬가지..

let n = Int(String(readLine()!))!
var dp: [[Int]] = Array(repeating: Array(repeating: 0, count: 10), count: 1001)

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

for i in stride(from: 2, through: n, by: 1){
    for j in 0...9 {
        for k in 0...j{
            dp[i][j] += dp[i - 1][k] % 10007
        }
    }
}
var sum = 0
for i in 0...9{
    sum += dp[n][i]
}
print(sum % 10007)