[Swift] BOJ 10844 쉬운 계단 수

BOJ 10844 쉬운 계단 수

 

✅ dp를 이용한 문제인데, 점화식을 찾았는데 이를 수학적으로 해결하려다가 시간이 매우 오래걸린 문제

 

일단 손으로 해보니까 일정한 패턴을 찾을 수 있었음

0 -> 1개

1~8 -> 2개

9 -> 1개

이렇게 노드를 만들 수 있었음.

 

처음에는 이를 해결하려고 수학적으로 접근을 했는데, 노드를 n = 4까지 직접 그려봐서 패턴을 찾으려고 함.

근데 이게 검증을 하려고 하니까 적어도 n = 5까지는 있어야할 것 같은데 너무 노가다인거 같은거임.

그래서 방법을 바꿈.

 

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]

 

이러한 패턴을 갖게 된다.

여기서 생각을 조금 쉽게 하는 방법이 레벨 1이 최하단 레벨(일의 자리)이라고 생각하고 거꾸로 찾아가는 과정이라고 생각하면 조금 더 논리적으로 이해하기가 편하다.

 

🤡 이상한 점

백준 코드에서 아래 for문에 2...input 이러니까 런타임에러 났음.이거 수정하니까 맞았다고 바뀌는데, 이유는 잘 모르겠다.

 

🟠 코드

//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)
    }
}