[Swift] 백준_쉬운 계단 수(10844)

문제

 

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

10844번: 쉬운 계단 수

 

 

풀이

 

수를 이어붙이는 문제여서 처음에는 앞자리와 연관을 지어서 생각했었다. result[k][1]은 n이 k일때 맨 앞자리가 1인 경우라고 생각하며 풀어보았지만 해결할 수 없어서 뒷자리를 이용해보기로했다.

 

그래서 result[k][i]는 n이 k일때 마지막 자리가 i인 경우로 생각했다. 이렇게 생각하니 마지막 자리수가 정해지면 나머지는 길이가 n - 1일때의 경우가 되는 것을 알 수 있었다.

 

따라서 식은 아래와 같이 구할 수 있었다.

 

result[k][i] = result[k - 1][i - 1] + result[k - 1][i + 1]

 

하지만 마지막 자리가 0일때는 앞자리가 1만 올 수 있고, 9일때는 8만 올 수 있다는 것을 생각해줘야한다.

import Foundation

let n = Int(readLine()!)!
if n == 1 {
    print(9)
    exit(0)
}
var result = Array(repeating: Array(repeating: 0, count: 10), count: n + 1)
for i in 1...9 {
    result[1][i] = 1
}
for i in 2...n {
    for j in 0...9 {
        if j == 0 {
            result[i][j] = result[i - 1][j + 1] % 1000000000
        } else if j == 9 {
            result[i][j] = result[i - 1][j - 1] % 1000000000
        } else {
            result[i][j] = (result[i - 1][j - 1] + result[i - 1][j + 1]) % 1000000000
        }
    }
}
print(result[n].reduce(0) { $0 + $1 } % 1000000000)

 

 

_____________________________________________________________________________________________________

 

 

아직 쉬운 문제들이지만 직접 식을 찾아서 해결하면 뿌듯함.