[Swift Algorithm] 1, 2, 3 더하기 BOJ #9095

문제 설명

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

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

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

 

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

 

입출력 예제

입력

3
4
7
10

출력

7
44
274

 

내 문제 풀이

let cases = Int(readLine()!)!

func solution(_ n: Int) -> Int {
    if n == 1 { return 1 }
    if n == 2 { return 2 }
    if n == 3 { return 4 }
    else { return solution(n-3) + solution(n-2) + solution(n-1) }
}

for _ in 0..<cases { print(solution(Int(readLine()!)!)) }

👉 DP 문제로, 점화식을 활용하여 재귀함수로 풀이하는것이 포인트!

[점화식]

• 1은 1 = 1개
• 2는 1+1 = 1개
• 3은 1+1+1, 1+2, 2+1 = 3개
• 4는 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1, 4 = 7개
• 5는 1+1+1+1, (1+1+1+2 X 4), (1+2+2 X 3), (1+1+3 X 3), (2+3 X 2), 5 = 13개

=> 이렇게 내가 구하고자 하는 수의 조합 개수는 이전 3개 수들의 조합 개수 합과 같음

=> solution(n) = solution(n-3) + solution(n-2) + solution(n-1) 으로 점화식 구현 가능!

 

[문제 풀이]

• n이 1, 2, 3일 경우는 이전 세 개 수 조합 개수를 구해줄 수 없으므로 예외로 처리했다.
• 그 외의 경우에는 모두 위에서 구한 점화식을 재귀 호출로 구현했다.

 

💡 피드백

• DP는 메모이제이션과 점화식을 사용해서 문제를 풀이하는 것 같다.
  여기서는 점화식을 구해주는게 관건이었는데, 다행히 어려운 패턴은 아니었다.
  하지만 앞으로 더 어려운,,! 점화식들을 생각해낼 수 있을지 걱정이 되긴 한다.
  점화식들도 특정한 패턴이나 유형이 있는지 많이 풀어봐야 알 수 있을 것 같다.

 

---

문제

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