[Swift 알고리즘] 백준 BOJ - 11057 오르막 수

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

 

오늘은 "백준 BOJ - 11057 오르막 수" 문제를 풀었습니다.

 

---

Github

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

 

문제 링크

11057번: 오르막 수

 

---

풀이

이번 문제는 DP를 이용한 문제입니다.

저는 한 가지를 놓쳐 굉장히 헤맸는데요.

 

괜히 한 번 더 생각한 로직

백준에는 오버플로우가 예상되는 문제에는 나머지 연산을 하게끔 하고 있습니다.

저도 마지막과 과정 중간에 나머지를 연산을 했는데요.

제가 처음 생각한 로직은 이 나머지 연산이 들어가면 사용 못 하는 로직이었습니다.

 

dp[1].append(contentsOf: Array(repeating: 1, count: 10))
if input >= 2 {
    for i in 2...input {
        dp[i].append(dp[i-1].reduce(0) { $0 + $1 } % MOD)
        for j in 1...9 {
            dp[i].append((dp[i][j-1] - dp[i-1][j-1]) % MOD)
        }
    }
}

저도 처음에는 일반적인 더하기 연산으로 값을 구해보려고 했습니다.

다만, 처음 한 번 합을 구하고 빼기 연산으로 다음 값을 구하면 반복 횟수가 줄어들지 않을까?라는 생각에 위와 같은 로직을 구상했는데요.

합이 10007이 넘어갈 경우 맨 첫 값이 작아서 마이너스 결과가 나오게 되었습니다.

테스트 케이스를 작은 수만 넣다보니 늦게까지 발견이 안 되었고 굉장히 헤맸습니다... ㅠㅠ

 

결국에는 처음 생각한 로직대로 더하기 연산을 이용해 결과를 구했습니다!

바로 정답이 되더라고요 ㅎㅎ...

 

오래 생각하는 게 마냥 좋지는 않은 듯 합니다.

 

---

전체 코드

//11057 오르막 수
import Foundation

let MOD = 10007
let input = Int(readLine()!)!

var dp: [Int] = Array(repeating: 1, count: 10)

for _ in 1..<input {
    for j in 1...9 {
        dp[j] = (dp[j-1] + dp[j]) % MOD
    }
}

print(dp.reduce(0, { ($0 + $1) % MOD }))

---

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

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

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