[백준/Swift] 10844번: 쉬운 계단 수

 

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

10844번: 쉬운 계단 수

 

맨 뒷자리 수 고정하고 진행! dp 2차원 배열~

이전에 여러 문제를 풀어본 결과, 공통점을 찾아야 한다. 그래서 이런 수를 가지고 문제를 풀어야 하는 경우 맨 뒤를 공통으로 맞추고 진행하면 좋다.

    0 1 2 3 4 5 6 7 8 9
-----------------------
1 | 0 1 1 1 1 1 1 1 1 1
2 | 1 1 2 2 2 2 2 2 2 1
3 | 1 3 3 4 4 4 4 4 3 2

이렇게 나열해 볼 수 있는데! 위에 표에서 보이는 대로 말하자면, 열은 마지막 수, 행은 자릿수를 나타낸다.

즉, 2행 4열은 2자리 수에서 4로 끝나는 계단 수의 개수라는 것!

여기서 처음에는 규칙이 하나도 안 보여서 좀 고민을 많이 했는데, 사실 규칙은 계단 수를 세면서 의연 중 알고 있었다! 의식하지 못했을 뿐...

3자리 수를 보면, 

232

234

321

323

343

345

432

434

이 수들을 보면 맨 마지막 수들이 바로 앞의 수에서 -1 / +1 되는 것을 알 수 있다! 그래서 이 생각을 하면서 다시 표를 보면

 dp[i-1][j-1] 와 dp[i-1][j+1] 의 합이 dp[i][j] 라는 것을 알 수 있다..!

대신 맨 앞(0)과 맨 뒤(9)는 당연히 안된다. 범위를 넘어서니까! 이들은 따로 처리해 주면 된다.

import Foundation

//input
let n = Int(readLine()!)!
var dp = [[Int]](repeating: [Int](repeating: 0, count: 10), count: n+2)
var answer = 0

for i in 1...9 {
    dp[1][i] = 1
}
if n > 1 {
    for i in 2...n {
        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 0...9 {
    answer += dp[n][i]
}
print(answer % 1000000000)