[Swift_알고리즘] 백준 15990_(1, 2, 3 더하기 5)

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

15990번: 1, 2, 3 더하기 5

 

흠... 그건.. 나도... 잘... 킥

 

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

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

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

입력

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

출력

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

 

 

풀이 방법

배열들을 쭉 적다보니 규칙이 보였음

A(1)은 1로 시작하는것이 1개, 2로시작하는 것이 0, 3으로 시작하는 것이 0 "1" -> [1, 0, 0]

A(2)은 1로 시작하는것이 0개, 2로시작하는 것이 1, 3으로 시작하는 것이 0  "2" -> [0, 1, 0]

A(3)은 1로 시작하는것이 1개, 2로시작하는 것이 1, 3으로 시작하는 것이 1 "1 + 2" "2 + 1" "3" -> [1, 1, 1]

 

이렇게 초기값을 세팅하면

A(4)는 A(3) 앞에 1을 붙인다고 생각했다. 이걸 풀어보자면 A(3) = "1 + 2, 2 + 1, 3"인데 앞에다가 1을 붙인다

A(4) = "1 + 1 + 2" , "1 + 2 + 1", "1 + 3"으로 생각하면 된다. 하지만 A(3)중 1로 시작하는 것은 사용할 수 없다. 이렇게 되면 1로 시작하는 경우의 수 A(4) = [?, ?, ?]중 첫번째 값은 A[3][1] +A[3][2]로 생각할 수 있다. 마찬가지로 두번째 ? 또한 방금 했던 것과 같이 계산 할 수 있다. -> A(4) = [A[3][1] + A[3][2] , A[2][0] + A[2][2] , A[1][0], A[1][1] ]

 

이것을 일반화 하면 A(n) = A(n-1)중 1로 시작하지 않는 경우의 수, A(n-2)중 2로 시작하지 않는 경우의 수, A(n-3)중 3으로 시작하지 않는 경우의수

 

 

func sol() {
  
    let target = Int(readLine()!)!
    var checkArr:[[Int]] = Array(repeating: [0], count: 100001)
    checkArr[1] = [1, 0, 0]
    checkArr[2] = [0, 1, 0]
    checkArr[3] = [1, 1, 1]
    let constVal = 1000000009
    
    var flag = 4
    for _ in 0...target - 1 {
        let inputVal = Int(readLine()!)!
        if checkArr[inputVal] == [0] {
            for j in flag...inputVal {
                checkArr[j] = [(checkArr[j - 1][1] + checkArr[j - 1][2]) % constVal, (checkArr[j - 2][2] + checkArr[j - 2][0]) % constVal, (checkArr[j - 3][0] + checkArr[j - 3][1]) % constVal]
                flag += 1
            }
        }
        print(checkArr[inputVal].reduce(0){$0 + $1} % constVal)
    }
}

sol()

 

 

checkArr[j] = [(checkArr[j - 1][1] + checkArr[j - 1][2]) , (checkArr[j - 2][2] + checkArr[j - 2][0]) , (checkArr[j - 3][0] + checkArr[j - 3][1])]

 

이런식으로 전 값을 알고 있다면 다음 값을 예측 할 수 있다.