[백준] (Swift) 10844번 - 쉬운 계단 수 (dp 기초 문제, 2차원 배열로 동적계획법 문제 풀기)

문제 링크

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

10844번: 쉬운 계단 수

 

풀이 IDEA

dp를 꾸준히 풀다보니, 어떤게 2차원으로 풀어야할지, 어떤게 일반 dp 1차원 배열로 풀어야할지 감이 잡혔다. 올레! 해당 문제는 N=1 부터 경우의수를 하나씩 따져가며 그림을 그려보니, 규칙이 눈에 보였다.

찾은 규칙은 아래와 같다.

위 그림을 보면, 맨 뒷자리수가 0과 9인 경우에는 한가지씩 늘어날 수 있고, 1~8 이라면 두가지의 경우로 늘어날 수 있다는 규칙을 찾아낼 수있다. 이를 dp 경우의수에 맞게 도식화 하면 아래와 같다.

• 현재 N에서, 0을 맨 뒷자리로 가지려면, N-1의 끝자리 1인 경우들이 와야한다.
  
  • dp[N][0] = dp[N-1][1]
• 현재 N에서, 9를 맨 끝자리로 가지려면, N-1의 끝자리 8인 경우이다.
  • dp[N][9] = dp[N-1][8]
• 현재 N에서, 1,2,3,4,5,6,7,8 을 맨 끝자리로 가지려면 N-1에서 앞뒤 숫자를 하나씩 가져와야한다. (총 2개)
  • dp[N][j] = dp[N-1][j-1] + dp[N-1][j+1]

위 세개의 점화식을, 조건문을 사용해서 코드를 구현했다. 구현한 소스코드는 아래와 같다. 문제 조건에서 주어진대로 1000000000을 나누어서 나머지를 출력해주었다.

let n = Int(readLine()!)!
var dp = [[Int]](repeating: Array(repeating: 0, count: 10), count: n+1)
var sum = 0

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

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

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


print(sum%1000000000)