BOJ-10844 쉬운 계단 수 Swift

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

내가 푼 풀이

- 길이 n의 계단 수를 구한다( 각 자리수의 차이가 1)

- i: 길이, j: 마지막자리의 숫자로 dp[i][j] 는 길이가 i인 마지막숫자 j가 오는 계단수의 갯수로 정의한다.

- dp[1][j] = 1 (  0 < j < 10 )

- 마지막자리 숫자가 0 인경우, 앞자리 수는 반드시 1 이와야하고, 마지막자리가 9라면, 앞자리 수는 반드시 8이어야 계단수가 성립한다.

- 나머지의 경우 는 마지막자리수 j의 앞자리수는 j-1 , j+1 이 될 수 있다.

- 이를 점화식으로 표현하면

• if j == 0 , dp[i][0] = dp[i-1][1]
• if j == 9 , dp[i][9] = dp[i-1][8]
• dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

- dp값을 넣어줄때 항상 10억으로 나눠주고, 결과도 10억으로 나눠서 출력한다.

 

import Foundation

let num = Int(String(readLine()!))!
var dp = Array(repeating: Array(repeating: 0, count: 10), count: num+1)

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

if num == 1 {
    print(dp[num].reduce(0, +))
} else {
    for i in 2...num {
        for j in 0...9 {
            if j == 0 {
                dp[i][j] = dp[i-1][1] % 1000000000
            } else if j == 9 {
                dp[i][j] = dp[i-1][8] % 1000000000
            } else {
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % 1000000000
            }
        }
    }
    
    print(dp[num].reduce(0, +) % 1000000000)
}