[백준 15989] 1, 2, 3 더하기 4 (Swift)

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

DP

정수 n을 입력받아서 그 수가 1,2,3 들의 합으로 만들어질 수 있는 경우의 수를 출력하는 문제.

순서는 상관없다.

 

접근방법

한참 고민하다가 다른 블로그를 보고 풀었는데, 풀이만 간단하게 써있는 걸로는 이해가 잘 안갔다.

대부분 점화식을 구해서 풀이하는 것 같았고, 가장 이해가 잘 됐던 설명은

1. 모든 수가 1로만 더해서 만들어 질 수 있는 경우를 1가지는 갖고 있음 -> 그래서 1부터 10000까지의 수에 해당하는 경우의 수를 1로 초기화한다.

- 1: 1

- 2: 1+1

- 3: 1+1+1

- 4: 1+1+1+1

2. 그리고 이제 각 수가 1과 2만 더해서 만들어질 수 있는 경우의 수를 구해서 더해주는데, 이는 본인(N)에서 2를 뺀 수(N-2)가 1로만 더해서 만들어질 수 있는 경우의 수에 2 하나를 더해서 만들 수 있는 경우이다. (근데 이 과정을 1부터 N까지 차례대로 실행해주면, 중간에 1과2를 더해서 만들어질 수 있는 수에 2 하나를 더해서 만들 수 있는 경우가 계산된다..흠 설명이 어려워서 예시를 들어서 설명하면)

- 1: 1

- 2: 1+1, 0+2 (0도 1개로 카운트됨)

- 3: 1+1+1, 1(3-2 = 1의 현재 경우)+2(2하나를 더하기)

- 4: 1+1+1+1, 1+1(4-2 = 2의 현재 경우)+2(2하나 더하기), 0+2(4-2의 현재 경우)+2(2하나 더하기)

3. 이제 1, 2, 3을 모두 써서 만들 수 있는 경우의 수는 2에서과 같이 N-3이 갖고 있는 경우의 수 만큼 본인에게 더해주면 된다. 그럼 3한개를 더한 만큼의 경우의 수가 나옴 

 

https://ku-hug.tistory.com/209 저는 이분 포스팅이 제일 이해하기 쉬웠음

 

오답노트

저는 처음에 cases에 숫자 더해갈 때 10000까지 반복문을 돌아야 하는데 N(문제에서는 T)까지 도는 오타를..범했음

여러분은 안그러시겠죠

 

소스코드

import Foundation

func solution() {
    
    let N = Int(readLine()!)!
    
    // process
    var cases:[Int] = [Int](repeating: 1, count: 100001)
    
    for i in 2...10000 {
        cases[i] += cases[i-2]
    }
    
    for i in 3...10000 {
        cases[i] += cases[i-3]
    }
    
    // in&output
    for _ in 0..<N {
        let n = Int(readLine()!)!
        print(cases[n])
    }
    
}

solution()