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의 합으로 나타내는 방법의 수를 출력한다.

 

====

문제 분석

정수를 1,2,3 으로 표현할 수있는 방법의 수를 저장하는 dp 를 선언한 후 

규칙을 찾아서 점화식을 만드는 문제

1. 문제를 봤을 때 규칙을 찾는게 쉽지 않아서 코드를 통해 1~100까지의 결과물들을 보면서 찾기로 결정

const main = (input) => {
    const dp = Array.from({ length: 10_001 }, () => []);
    dp[1] = [[1]];
    dp[2] = [[1, 1], [2]];
    dp[3] = [[1, 1, 1], [2, 1], [3]];
    dp[4] = [
        [1, 1, 1, 1],
        [2, 1, 1],
        [3, 1],
        [2, 2],
    ];

    for (let i = 5; i < 50; i++) {
        const temp = [];
        dp[i - 1].forEach((arr) => {
            temp.push([...arr, 1].sort((a, b) => a - b));
        });
        dp[i - 2].forEach((arr) => {
            temp.push([...arr, 2].sort((a, b) => a - b));
        });
        dp[i - 3].forEach((arr) => {
            temp.push([...arr, 3].sort((a, b) => a - b));
        });

        // 중복 제거
        const uniqueTemp = temp
            .map(JSON.stringify)
            .filter((v, i, a) => a.indexOf(v) === i)
            .map(JSON.parse);
        dp[i] = uniqueTemp;
        console.log();
        console.log(
            i,
            ':',
            dp[i].length,
            '차이',
            dp[i].length - dp[i - 1].length
        );
        console.log('===========');
    }
};

위 코드의 출력값을 보면 6의 배수를 기준으로 diff가 1씩 증가하고 6의 배수의 다음 수는 diff-1을 이전 dp[i-1]에 더하면 된다는 것을 발견

5 : 5 차이 1
===========

6 : 7 차이 2
===========

7 : 8 차이 1
===========

8 : 10 차이 2
===========

9 : 12 차이 2
===========

10 : 14 차이 2
===========

11 : 16 차이 2
===========

12 : 19 차이 3
===========

13 : 21 차이 2
===========

14 : 24 차이 3
===========

15 : 27 차이 3
===========

16 : 30 차이 3
===========

17 : 33 차이 3
===========

18 : 37 차이 4
===========

19 : 40 차이 3
===========

20 : 44 차이 4
===========

21 : 48 차이 4
===========

22 : 52 차이 4
===========

23 : 56 차이 4
===========

24 : 61 차이 5
===========

25 : 65 차이 4
===========

26 : 70 차이 5
===========

27 : 75 차이 5
===========

28 : 80 차이 5
===========

29 : 85 차이 5
===========

30 : 91 차이 6
===========

31 : 96 차이 5
===========

32 : 102 차이 6
===========

33 : 108 차이 6
===========

34 : 114 차이 6
===========

35 : 120 차이 6
===========

36 : 127 차이 7
===========

37 : 133 차이 6
===========

38 : 140 차이 7
===========

39 : 147 차이 7
===========

40 : 154 차이 7
===========

41 : 161 차이 7
===========

42 : 169 차이 8
===========

43 : 176 차이 7
===========

44 : 184 차이 8
===========

45 : 192 차이 8
===========

46 : 200 차이 8
===========

47 : 208 차이 8
===========

48 : 217 차이 9
===========

49 : 225 차이 8

 

위에서 찾은 규칙을 코드화 하여 아래의 결과를 제출했더니 맞았다

정답 코드

const main = (input) => {
    const dp = Array.from({ length: 10_001 }, () => []);
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 3;
    dp[4] = 4;
    dp[5] = 5;
    dp[6] = 7;
    let dif = 2;
    for (let i = 7; i < 10_001; i++) {
        if (i % 6 === 0) {
            dif += 1;
            dp[i] = dp[i - 1] + dif;
        } else if (i % 6 === 1) {
            dp[i] = dp[i - 1] + dif - 1;
        } else {
            dp[i] = dp[i - 1] + dif;
        }
    }
    const answer = [];
    for (let i = 1; i < input.length; i++) {
        const idx = +input[i];
        if (i === input.length - 1) {
            answer.push(`${dp[idx]}`);
        } else {
            answer.push(`${dp[idx]}\n`);
        }
    }
    console.log(answer.join(''));
};
const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

main(input);