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로 나눈 나머지를 출력한다.

===

문제 분석

기존에 풀었던 1,2,3 더하기 문제에서는 1차원 배열 dp를 선언한 뒤 dp[i] = dp[i]+dp[i-num (num range 1~3)]  시전해주면 되었다.

이 문제에서는 연속된 수의 덧셈을 지향해야한다는 특이점이 있다.

이 특이점을 해결하기 위해선 각 index의 조합 수를 구할 때 마지막으로 사용한 num에 따라 나눠서 기록하는 방법이 있다.

예를 들어 1,2,3을 사용하여 5를 만들 땐 4,3,2 에서 조합을 가져와야 하는데

4를 만든 숫자들의 조합에서 마지막으로 1을 사용한 조합은 제외한 경우

3을 만든 숫자들의 조합에서 마지막으로 2를 사용한 조합은 제외한 경우

2를 만든 숫자들의 조합에서 마지막으로 3을 사용한 조합은 제외한 경우

이를 위해 각 dp에 인덱스 1,2,3 을 넣어서 각 인덱스에 경우의 수를 기록한다.

const MAX = 100_001;
const INF = 1_000_000_009;
const dp = Array.from({ length: MAX }, () => [0, 0, 0, 0]);

인덱스 그대로 1,2,3을 사용하기 위해 앞에 사용하지 않는 0을 추가하여 [0,0,0,0]을 넣은 것이다.

우선 기본적으로 알고 있는 dp를 기록

dp[1][1] = 1;
dp[2][2] = 1;
dp[3][1] = 1;
dp[3][2] = 1;
dp[3][3] = 1;

아래는 현재 수를 만들 때 1~3을 사용하는 경우의 수를 체크한 뒤 diff에서 사용중인 1~3은 제외하면서 dp[cur]에 기록하는 법

for (let cur = 4; cur < MAX; cur++) {
    for (let num = 1; num < 4; num++) {
        const diff = cur - num;
        for (let col = 1; col < 4; col++) {
            if (col === num) continue;
            dp[cur][num] = (dp[cur][num] + dp[diff][col]) % INF;
        }
    }
}

각 행의 합이 정답이 되므로

console.log(
    arr
        .map((v) => {
            return dp[v].reduce((acc, cur) => (acc + cur) % INF, 0);
        })
        .join('\n')
);

정답 코드

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const T = +input[0];
const arr = [];
for (let i = 1; i < T + 1; i++) {
    arr.push(+input[i]);
}

const MAX = 100_001;
const INF = 1_000_000_009;
const dp = Array.from({ length: MAX }, () => [0, 0, 0, 0]);
dp[1][1] = 1;
dp[2][2] = 1;
dp[3][1] = 1;
dp[3][2] = 1;
dp[3][3] = 1;

for (let cur = 4; cur < MAX; cur++) {
    for (let num = 1; num < 4; num++) {
        const diff = cur - num;
        for (let col = 1; col < 4; col++) {
            if (col === num) continue;
            dp[cur][num] = (dp[cur][num] + dp[diff][col]) % INF;
        }
    }
}

console.log(
    arr
        .map((v) => {
            return dp[v].reduce((acc, cur) => (acc + cur) % INF, 0);
        })
        .join('\n')
);