[백준] 1,2,3 더하기 3 (15988번)

문제 내용

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

n = 4 이라고 하면

1 + 1 + 1 + 1,

1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1

2 + 2,

1 + 3, 3 + 1

이렇게 총 7개가 되어 7을 print 하면 된다.

 

첫 줄에 테스트 케이스의 개수 T 가 주어지고

T 번동안 정수 n 이 주어진다.

방법의 수를 1,000,000,009 로 나눈 나머지를 출력

---

전체 코드

// 1. n 의 최댓값이 1,000,000 이므로 배열의 크기를 1,000,001 만큼 생성하였음
var arr: [Int] = Array(repeating: 0, count: 1_000_001)
// 2. 어디까지 값을 최신화하였는지 저장할 값
var complete = 3
// 3. 나누는 수
let div = 1_000_000_009

// 4. 초기 값 설정
arr[1] = 1
arr[2] = 2
arr[3] = 4

// 5. 초기 테스트 케이스 만큼 반복
for _ in 0..<Int(readLine()!)! {
    // 6. n 값 받음
    let n = Int(readLine()!)!
    
    // 7. 만약 n 이 최신화된 값보다 크면
    if n > complete {
        // 8. 최신화된 값부터 n 까지 값을 갱신
        for i in complete+1...n {
            // 9. arr[i] = arr[i - 1] + arr[i - 2] + arr[i - 3] 인데
            // div 로 나눈 나머지로 갱신해야 하므로 각각 div 로 % 해주었음
            arr[i] = ((arr[i - 1] % div) + (arr[i - 2] % div) + (arr[i - 3] % div)) % div
        }
        // 10. 최신화된 값을 n 으로 설정
        complete = n
    }
    // 11. 값 출력
    print(arr[n])
}

---

결론

arr[n] = arr[n - 1] + arr[n - 2] + arr[n -3] 이라는 걸 알면 풀 수 있는 문제

 

출처 : 백준 1, 2, 3 더하기 3
https://www.acmicpc.net/problem/15988

15988번: 1, 2, 3 더하기 3