[Swift] BOJ 10844 쉬운 계단 수

BOJ 10844 쉬운 계단 수

 

접근 방식

 

마지막 자리 숫자를 상태로 두는 DP. dp[N][L]은 길이 N인 계단 수 중 마지막 자리가 L인 개수를 뜻함. 계단 수는 이웃한 자리의 차가 1이므로, 마지막이 L이면 그 앞자리는 L-1이나 L+1이어야 함. 여기서 점화식이 나옴.

 

• 0 : dp[N][L] = dp[N-1][L+1]
• 1~8 : dp[N][L] = dp[N-1][L+1] + dp[N-1][L-1]
• 9 : dp[N][L] = dp[N-1][L-1]

 

0은 앞에 1만, 9는 앞에 8만 올 수 있어서 더할 항이 하나뿐임. 1~8은 양쪽에서 오므로 두 항을 더함.

 

한 자리 계단 수는 1~9가 각각 하나씩이라 dp[1][1...9] = 1로 시작함(0은 맨 앞에 못 옴). 마지막 행 dp[input]의 합이 답이고, 각 항마다 10^9로 나눈 나머지를 취함.

 

처음에는 손으로 n = 4까지 그려 닫힌 식을 찾아 풀려고 했는데, 검증하려면 n = 5까지는 그려야 해서 수작업이 비효율적이라 판단하고 DP 테이블로 바꿈.

 

시행착오

 

백준 제출 코드에서 for문을 2...input으로 작성하니 런타임 에러가 났고, 2..<input+1로 바꾸니 통과함. input이 1이면 2...input이 2...1이 되는데, 하한이 상한보다 큰 범위라 그 자리에서 크래시가 남. 2..<input+1은 빈 범위로 처리되어 안전함.

 

코드

 

//https://www.acmicpc.net/problem/10844
import Foundation

struct b10844 {
    
    static func run() {
        // DP를 이용하여 풀어야 합니다.
        let input: Int = Int(readLine()!)!
        var dp = [[Int]](repeating: [Int](repeating: 0, count: 11), count: input+1)
//        print(dp)
        
        for i in 1...9 {
            dp[1][i] = 1
        }
        
        for N in 2..<input+1{ // 2...input 이러면 runtime error남
            for L in 0...9 {
                if L == 0 {
                    dp[N][L] = dp[N-1][L+1] % 1000000000
                } else if L == 9 {
                    dp[N][L] = dp[N-1][L-1] % 1000000000
                } else {
                    dp[N][L] = (dp[N-1][L-1] + dp[N-1][L+1]) % 1000000000
                }
            }
        }
        
        var sum = 0
        dp[input].forEach {
            sum += $0
        }
        print(sum % 1000000000)
    }
}