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

요구능력 : DP와 2차원 배열을 이용한 규칙

 

코드설명 : 

계단수라고 하여서 1의 자리는 안될거 같았는데 예제보니까 됩니다.

길이가 N인 계단 수라서 N = 1이면 한자리 N = 2이면 두자리입니다.

 

n = 1

1, 2, 3, 4, 5, 6, 7, 8, 9

 

n = 2

12, 21

23, 32

34, 43

45, 54

56, 65

67, 76

78, 87

89, 98

10

 

여기까지만 보고 직접 n = 3일때를 맨뒷자리 기준으로 하나만 적어보면

n = 3

dp[3][3]

123

323

543

343 이 됩니다.

 

맨뒷자리 기준으로 봤을 때 배열을 dp[i][j]라고 하면 3앞에 2와 4는 j - 1과 j + 1이 됩니다.

그리고 2와 4의 앞에 1과 3 5와 3 또한 j - 1과 j + 1이 됩니다.

이렇게 중복되는 부분문제가 발생하기 때문에 DP로 풀 수 있는것입니다.

 

그리고 맨뒷자리가 3일 때 앞의 자리 숫자들 (12)3, (32)3, (54)3, (34)3 은 dp[i - 1][j -1]과 dp[i - 1][j + 1]에서 가져온것입니다.

큰 문제가 쪼개지는 DP의 특성입니다.

 

결론적으로, 점화식은 dp[i][j] = dp[i - 1][j + 1] + dp[i - 1][j - 1] 이 성립하게 된다.

 

1. dp[1]과 dp[2]를 따로 정의해준다.

 

2. j는 0일때와 9일때를 따로 처리해주는 이유는 0은 [j - 1]이 안되고 9는 [j + 1]이 안되기 때문이다.

 

 

후기 : 백준 15990번이 아주 도움이 많이됬다.. 규칙찾으려고 수를 나열하고 혹시나해서 맨뒤 수를 고정하고 2차원배열로 풀어봤는데 너무 쉽게 풀렸다.

 

let n = Int(readLine()!)! //수의 길이
var dp = Array(repeating: Array(repeating: 0, count: 10), count: 101)
var sum = 0

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

dp[2][0] = 1
dp[2][1] = 1
dp[2][2] = 2
dp[2][3] = 2
dp[2][4] = 2
dp[2][5] = 2
dp[2][6] = 2
dp[2][7] = 2
dp[2][8] = 2
dp[2][9] = 1

for i in stride(from: 3, through: n, by: 1) {
    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 {
    sum += dp[n][i]
}

print("\(sum % 1000000000)")