백준 9095 — 1, 2, 3 더하기: 마지막 숫자로 경우 나누기

백준 9095 문제 보기

문제

1. 테이블 정의하기

D[i] = i를 1, 2, 3의 합으로 나타내는 경우의 수

2. 점화식 찾기

예시 갖고 생각해보기

• D[4] 를 예시로 생각하면, 아래 7 경우가 존재한다.

  Text

  1 + 1 + 1 + 1 : 합이 3인 식 뒤에 1을 붙임
  1 + 1 + 2 : 합이 2인 식 뒤에 2를 붙임
  1 + 2 + 1 : 합이 3인 식 뒤에 1을 붙임
  2 + 1 + 1 : 합이 3인 식 뒤에 1을 붙임
  2 + 2 : 합이 2인 식 뒤에 2를 붙임
  1 + 3 : 합이 1인 식 뒤에 3을 붙임
  3 + 1 : 합이 3인 식 뒤에 1을 붙임

  • 분석하면 D[4] = D[1] + D[2] + D[3]이다.

D[i] = D[i - 1] + D[i - 2] + D[i - 3]

D[i]는 합 자체가 아니라 식을 만드는 경우의 수다. 마지막에 1을 붙이는 경우는 D[i - 1]개이며, 여기에 숫자 1을 더하는 것은 아니다. 마지막 숫자가 서로 다른 세 집합은 겹치지 않으므로 경우의 수를 더할 수 있다. 1+2와 2+1은 서로 다른 경우로 센다.

3. 초기값 정의하기

D[4] 정의를 위해 D[1], D[2], D[3]가 필요하므로 이 구현에서는 이 세 값을 초기값으로 둔다.

D[1] = 1 (1)
 
D[2] = 2 (1 + 1, 2)
 
D[3] = 4 (1 + 1 + 1, 1 + 2, 2 + 1, 3)

4. 코드 구현하기

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
 
const [T, ...inputs] = fs.readFileSync(filePath, 'utf-8').trim().split('\n').map(Number);
 
function solution(N) {
    // 배열 생성
    const DP = Array.from({ length: N + 1 }).fill(0);
 
    // 초기값 설정
    DP[1] = 1;
    DP[2] = 2;
    DP[3] = 4;
 
    // DP 계산 - for문
    for (let i = 4; i <= N; i++) {
        // 점화식
        DP[i] = DP[i - 1] + DP[i - 2] + DP[i - 3];
    }
 
    console.log(DP[N]);
}
 
for (let i = 0; i < T; i++) {
    solution(inputs[i]);
}

복잡도

테스트 케이스 하나당 시간 O(N), DP 테이블 공간 O(N). 여러 케이스에서는 각 N에 대한 계산 시간이 합산된다.

참고 자료

바킹독의 실전 알고리즘 0x10강 — 다이나믹 프로그래밍을 학습하며 작성한 메모를 바탕으로 정리했다. 포함된 이미지는 원본 학습 메모의 캡처다.