[Swift 알고리즘] 백준 BOJ - 9095 1, 2, 3 더하기

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

 

오늘은 "백준 BOJ - 9095 1, 2, 3 더하기" 문제를 풀었습니다.

 

---

Github

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

 

문제 링크

9095번: 1, 2, 3 더하기

 

---

풀이

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

 

숫자 n이 입력됐을 때 1, 2, 3의 합을 이용해 만들 수 있는 경우의 수를 출력해야 합니다.

n이 1, 2, 3일 때의 각 케이스는 아래와 같습니다.

1	1
2	1+1, 2
3	1+1+1, 1+2, 2+1, 3

예시를 보면 알겠지만 1+2, 2+1은 서로 다른 케이스입니다.

 

그럼 4는 몇 가지가 있을까요?

1+1+1+1, 1+2+1, 2+1+1, 3+1, 1+1+2, 2+2, 1+3로 총 7가지가 있습니다.

규칙을 알아채기 쉽도록 순서에 맞춰 적어보았는데요.

혹시 규칙을 발견 하셨나요??

 

dp[i]는 dp[i-1]에 +1을, dp[i-2]에 +2를, dp[i-3]에 +3을 한 것입니다.

이를 수식으로 나타내면 아래와 같습니다.

dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

 

위 수식을 이용해 코드를 작성하면 답을 구할 수 있습니다.

 

---

전체 코드

//9095 1, 2, 3 더하기
import Foundation

let count = Int(readLine()!)!
for _ in 0..<count {
    let input = Int(readLine()!)!
    var dp: [Int] = [0, 1, 2, 4]
    if input >= 4 {
        for i in 4...input {
            dp.append(dp[i-1] + dp[i-2] + dp[i-3])
        }
    }
    print(dp[input])
}

---

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

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

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