[Swift] 9095번: 1, 2, 3 더하기 문제 풀이 [BOJ - Silver3]

💬 문제

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

9095번: 1, 2, 3 더하기

 

이 문제는 DP의 기본문제라고 할 수 있습니다.

그치만 아직 DP가 익숙하지 않아서 점화식이 바로바로 떠오르지가 않았기에 깊게 고민이 필요했어요..

후우 뭔가 알 것 같은데.. 규칙이 보일 것 같은데, 머릿속에서 얽혀버려서 결국 다른 풀이를 참고했습니다!

 

풀이를 참고하고 보니 접근법까지는 맞았는데, 어느샌가 1, 2, 3의 합으로 나타내는 이라는 중요한 key point를 놓치고 있었어요.

진짜 DP는 풀이를 참고하면 할수록 신세계인 것 같아요 .. 어떤 분이 블로그에 고민하다가 보는 DP 풀이는 정말 신세계고 그런걸 많이많이 경험해보라 하셨는데 너무너무 공감이 가네요! ㅎㅎ

 

제 블로그를 참고하시는 여러분도 DP의 신세계를 경험하는데 조금이나마 도움이 되길 바라며 풀이를 올려보겠습니다!

 

---

💬 Idea

바텀업 방식으로 DP를 구현

 

[기본 정보]

1	1	1가지
2	1 + 1 2	2가지
3	1 + 1 + 1 1 + 2 2 + 1 3	4가지

기본적으로 1, 2, 3은 각각 1, 2, 3의 합으로 나타내는 방법으로 1, 2, 4가지의 방법을 갖고 있습니다.

 

 

[규칙]

그럼 다음으로 4가 어떻게 만들어질 수 있는지 살펴보겠습니다!

4	1 + 3 2 + 2 3 + 1

 

💡 4를 만들 때 1을 포함하여 4를 만들려면 → 3이라는 숫자가 필요
이 때 3을 1, 2, 3의 합으로 나타내는 방법은 4가지라는 것을 우리는 이미 알고 있음
→ 따라서 숫자 4를 1 + 3의 조합으로 만들 수 있는 방법은 4가지

• 1 + 3
• 1 + 1 + 2
• 1 + 2 + 1
• 1 + 1 + 1 + 1

 

💡 4를 만들 때 2를 포함하여 4를 만들려면 → 2라는 숫자가 필요

이 때 2을 1, 2, 3의 합으로 나타내는 방법은 2가지라는 것을 우리는 이미 알고 있음

→ 따라서 숫자 4를 2 + 2의 조합으로 만들 수 있는 방법은 2가지

• 2 + 1 + 1
• 2 + 2

 

💡 4를 만들 때 3을 포함하여 4를 만들려면 → 1이라는 숫자가 필요

이 때 1을 1, 2, 3의 합으로 나타내는 방법은 1가지라는 것을 우리는 이미 알고 있음

→ 따라서 숫자 4를 3 + 1의 조합으로 만들 수 있는 방법은 1가지

• 3 + 1

 

따라서 최종적으로 4를 1, 2, 3의 합으로 나타내는 방법은 7가지 입니다.

여기서 볼 수 있는 규칙은 4가 이전 세개의 항인 1, 2, 3이 가지는 방법의 수를 더한 개수만큼 방법을 가진다는 것인데요,

4	1 + 3	1 + 3 1 + 1 + 2 1 + 2 + 1 1 + 1 + 1 + 1
	2 + 2	2 + 1 + 1 2 + 2
	3 + 1	3 + 1
		합: 4 + 2 + 1 = 7

1 - 1개

2 - 2개

3 - 4개

4 - 7개 == 1 + 2 + 4

 

 

✅ 규칙을 확실히 알아보기 위해서 정수 5를 1, 2, 3의 합으로 나타내는 방법도 한번 살펴보도록 합시다!!

5	1 + 4 2 + 3 3 + 2

 

💡 5를 만들 때 1을 포함하여 5를 만들려면 → 4라는 숫자가 필요

이 때 4을 1, 2, 3의 합으로 나타내는 방법은 7가지라는 것을 우리는 이미 알고 있음

→ 따라서 숫자 5를 1 + 4의 조합으로 만들 수 있는 방법은 7가지

• 1 + 1 + 1 + 1 + 1
• 1 + 1 + 1+ 2
• 1 + 1 + 2 + 1
• 1 + 1 + 3
• 1 + 2 + 1 + 1
• 1 + 2+ 2
• 1 + 3 + 1

 

💡 5를 만들 때 2를 포함하여 5를 만들려면 → 3이라는 숫자가 필요

이 때 3을 1, 2, 3의 합으로 나타내는 방법은 4가지라는 것을 우리는 이미 알고 있음

→ 따라서 숫자 5를 2 + 3의 조합으로 만들 수 있는 방법은 4가지

• 2 + 1 + 1 + 1
• 2 + 1 + 2
• 2 + 2 + 1
• 2 + 3

 

💡 5를 만들 때 3을 포함하여 5를 만들려면 → 2라는 숫자가 필요

이 때 2를 1, 2, 3의 합으로 나타내는 방법은 2가지라는 것을 우리는 이미 알고 있음

→ 따라서 숫자 5를 3 + 2의 조합으로 만들 수 있는 방법은 2가지

• 3 + 1 + 1
• 3 + 2

따라서 최종적으로 5를 1, 2, 3의 합으로 나타내는 방법은 13가지 입니다. (7 + 4 + 2)

5	1 + 4	1 + 1 + 1 + 1 + 1 1 + 1 + 1+ 2 1 + 1 + 2 + 1 1 + 1 + 3 1 + 2 + 1 + 1 1 + 2+ 2 1 + 3 + 1
	2 + 3	2 + 1 + 1 + 1 2 + 1 + 2 2 + 2 + 1 2 + 3
	3 + 2	3 + 1 + 1 3 + 2
		합: 7 + 4 + 2 = 13

 

5를 나타내는 방법까지 알아보고 나니 이제 규칙이 확실해진 것 같지 않나요?

 

4를 나타내는 방법을 도출하기 위해 알아야 했던 수가 (1 + 3, 2 + 2, 3 + 1) 3, 2, 1 이었고,

5를 나타내는 방법을 도출하기 위해 알아야 했던 수가 (1 + 4, 2 + 3, 3 +2) 4, 3, 2 였습니다.

 

6을 나타내는 방법을 도출하기 위해 알아야 하는 수는 (1 + 5, 2 + 4, 3 + 3) 5, 4, 3 일테고

7을 나타내는 방법을 도출하기 위해 알아야 하는 수는 (1 + 6, 2 + 5, 3 + 4) 6, 5, 4 이겠죠?

 

 

즉 어떤 정수 n을 1, 2, 3의 합으로 나타내는 방법을 알기 위해서는
→ 이전 세개의 항 각각의 방법의 개수를 알고 있다면 해결할 수 있게 된다는 말입니다.

 

따라서 이 문제의 점화식은 아래와 같이 표현할 수 있습니다.

 

원리를 이해하고 나니 "한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘인 DP"와 참 찰떡콩떡 인 문제죠 ~?

위 아이디어를 코드로 표현하면 아래와 같습니다!

 

---

💬 풀이

import Foundation

func solution9095() {
    let TC = Int(readLine()!)!
    var sumCaseArr = Array(repeating: 0, count: 11)
    
    sumCaseArr[1] = 1
    sumCaseArr[2] = 2
    sumCaseArr[3] = 4
    
    for i in 4...10 {
        sumCaseArr[i] = sumCaseArr[i - 1] + sumCaseArr[i - 2] + sumCaseArr[i - 3]
    }
    
    for _ in 0..<TC {
        let n = Int(readLine()!)!
        print(sumCaseArr[n])
    }
}

DP.. 간단한 문제인데도 참 어렵네요!!

그렇지만 중요한건 꺾이지 않는 마음이겠죠! 😊 👊🏻 😊 👊🏻 

 

 

 

https://github.com/hwangJi-dev/swiftAlgorithm/blob/main/Programmers/Boj/9095_1%2C%202%2C%203%20%EB%8D%94%ED%95%98%EA%B8%B0.swift

GitHub - hwangJi-dev/swiftAlgorithm: Algorithm Practice with Swift