[Swift 알고리즘] 백준 BOJ - 10844 쉬운 계단 수

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "백준 BOJ - 10844 쉬운 계단 수" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

10844번: 쉬운 계단 수

 

---

풀이

이번 문제는 DP문제입니다.

이전 문제들보다는 규칙을 찾는게 힘들었습니다 ㅠㅠ

 

이번 문제에서는 1의 자리가 포인트입니다. 이전 숫자들에 1의 자리를 추가한다는 흐름입니다.

0~9까지 1의 자리에 올 수 있는 경우의 수를 세는 것이죠.

 

1의 자리에 0이 오기 위해서는 바로 앞에 1이 와야 합니다.

이 경우의 수는 i-1의 1이 1의 자리에 온 경우의 수와 동일합니다.

 

9가 1의 자리에 오기 위해서는 앞에 8이 와야 하므로 이 경우의 수는 동일한 원리로 i-1의 8이 1의 자리에 온 경우의 수와 같습니다.

 

1~8은 어떨까요?

1은 0, 2가 앞에 올 경우, 2는 1, 3이 앞에 올 경우 ... 입니다.

따라서 1~8의 경우의 수는 i-1의 1의 자리가 j-1, j+1인 경우의 수를 더한 값입니다.

 

이를 케이스별로 나눠 생각하면 아래처럼 표현할 수 있습니다.

for i in 2...input {
        for j in 0...9 {
            switch j {
            case 0:
                dp[i].append(dp[i-1][j+1])
            case 9:
                dp[i].append(dp[i-1][j-1])
            default:
                dp[i].append((dp[i-1][j-1] + dp[i-1][j+1]))
            }
        }
    }

 

이를 이용해 문제를 해결하면 됩니다.

각 연산마다 10억을 나머지 연산 해주는 것도 잊지 마세요!

 

---

전체 코드

//10844 쉬운 계단 수
import Foundation

let MOD = 1000000000

let input = Int(readLine()!)!
var dp: [[Int]] = Array(repeating: [], count: input+1)

dp[1].append(0)
for _ in 1...9 {
    dp[1].append(1)
}

if input >= 2 {
    for i in 2...input {
        for j in 0...9 {
            switch j {
            case 0:
                dp[i].append(dp[i-1][j+1] % MOD)
            case 9:
                dp[i].append(dp[i-1][j-1] % MOD)
            default:
                dp[i].append((dp[i-1][j-1] + dp[i-1][j+1]) % MOD)
            }
        }
    }
}

print(dp[input].reduce(0) { ($0 + $1) % MOD })

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.