[Swift 알고리즘] 백준 15989 (1, 2, 3더하기)

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

15989번: 1, 2, 3 더하기 4

 

 

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다.

• 1+1+1+1
• 2+1+1 (1+1+2, 1+2+1)
• 2+2
• 1+3 (3+1)

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

입력

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

출력

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

 

풀이방법

dp[n]을 1로 시작하는 수, 2로 시작하는 수, 3으로 시작하는 수 이렇게 나누어서 풀었습니다. 그렇게 된다면 dp[n]일 때 이전 숫자들을 통해 값을 전해 받을 수 있습니다. 숫자를 정렬함에 있어서 마구잡이가 아닌 내림차순으로 정렬하는것을 키포인트로 하였습니다.

 

 

 

이렇게 초기값을 세팅 할 수 있습니다.

 

 

dp를 진행함에 있어서 다음과 같이 진행합니다.

 

 

 

 

 

 

 

 

dp[4][2] :  ind가 4 - 3 에서 모든 숫자를 올려 받습니다. 시작을 3으로 하고 현재ind 에서 3을 뺏기 때문에 모든 숫자는 3보다 작거나 같습니다.

dp[4][1] : ind가 4-2 에서 3으로 시작하는 숫자를 제외한 모든 숫자를 올려 받습니다. 시작을 2로하기 때문에 중간에 3이 들어가면 안됩니다.

dp[4][0] : ind가 4-3에서 2와 3으로 시작하는 숫자를 제외한 모든 숫자를 올려 받습니다. 시작을 1로 하기에 중간에 2와 3이 들어가면 안됩니다. 

 

일단 이렇게 초기화 할 수 있습니다. 마찬가지로 5와 6또한 다음과 같이 업데이트 할 수 있습니다.

 

dp[5]일때 모든 숫자를 출력한다.

 

dp[6]일때 모든 숫자를 출력한다.

 

 

 

이를 Count로 바꿔서 계산해주면 됩니다.

 

전체 코드

func sol() {
    var dp:[[Int]] = [[0, 0, 0], [1, 0, 0], [1, 1, 0], [1, 1, 1]]
    var dpCount = 3
    for _ in 0..<Int(readLine()!)! {
        let cur = Int(readLine()!)!
        while dpCount < cur {
            dpCount += 1
            var temp = [0, 0, 0]
            temp[0] = 1
            temp[1] = dp[dpCount - 2][0] + dp[dpCount - 2][1]
            temp[2] = dp[dpCount - 3][0] + dp[dpCount - 3][1] + dp[dpCount - 3][2] 
            dp.append(temp)
        }
        print(dp[cur].reduce(0){$0 + $1})
    }
}
sol()

 

 

 

 

오늘 날씨가 32도까지 올라가네요. 여름이니까 김애란씨의 바깥은 여름 추천합니당 🥳