[Swift] 백준 10844 - 쉬운 계단 수

문제 링크

문제를 풀기 위해서 하나하나 작성해보면 다음과 같은 규칙을 찾을 수 있습니다.

첫번째 숫자가

• 1에서 8까지는
  • dp[3][i] = dp[2][i-1] + dp[2][i+1]
• 0일때는
  • dp[3][0] = dp[2][1]
• 9일때는
  • dp[3][9] = dp[2][8]

0으로 시작하는 계단수는 없지만 dp[3][1]인 경우 dp[2][0]의 값을 알아야하기 때문에 dp[2][0]의 값은 알아야합니다.

최종 풀이

import Foundation

let num = Int(readLine()!)!
var dp = Array(repeating: Array(repeating: 0, count: 10), count: 101)
var sum = 0

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

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

for i in 1...9 {
    sum = (sum + dp[num][i]) % 1000000000
}

print(sum % 1000000000)

• 이때 dp[num][0]은 계산을 위해 사용한 값이지 계단수는 아니기 때문에 1에서 9까지의 값만 더해줍니다.