백준 9095번 1,2,3 더하기 - node.js

#백준

#JavaScript

#DP

박효진 (@gywlsp)

2020년 11월 18일

이 글은 백준 백준 9095번 1,2,3 더하기를 풀이한다. 문제 링크
코드는 javascript로 작성하였다.

문제 파악

  • 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때에는 수를 1개 이상 사용해야 한다.

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

입력

  • 첫째 줄에 테스트 케이스의 개수 T가 주어진다. (범위 명시 안 되어있음)
  • 둘째 줄부터 N개의 줄에는 정수 n(0<n<11)이 주어진다.

예제 입력

3
4
7
10

출력

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

예제 출력

7
44
274

시간 제한

  • 1초

메모리 제한

  • 128MB

문제 풀이

접근

예제 입력을 보며 답을 어떻게 낼 수 있을지 생각해보자.
정수 4를 1, 2, 3의 합으로 나타내는 방법은 다음 세가지 경우의 합이다.

  1. 정수 1(4-1)을 1, 2, 3의 합으로 나타내는 방법에 3을 포함해서 나타내는 방법
  2. 정수 2(4-2)을 1, 2, 3의 합으로 나타내는 방법에 2을 포함해서 나타내는 방법
  3. 정수 3(4-3)을 1, 2, 3의 합으로 나타내는 방법에 1을 포함해서 나타내는 방법

합쳐진 방법들이 중복되지 않도록 하기 위해서는 어떻게 해야 할까?
정수 1, 2, 3 각각을 1, 2, 3의 합으로 나타내는 방법은 다음과 같다.

  1. 정수 1을 1, 2, 3의 합으로 나타내는 방법

    • 1

  2. 정수 2를 1, 2, 3의 합으로 나타내는 방법

    • 1, 1
    • 2

  3. 정수 3을 1, 2, 3의 합으로 나타내는 방법

    • 1, 1, 1
    • 1, 2
    • 2, 1
    • 3

정수 n을 나타내는 각 방법의 뒤에 4-n을 써주어 정수 4를 나타내는 방법을 나열하면 다음과 같다.

  1. 정수 1의 방법들로 정수 4를 나타내는 방법

    • 1, 3

  2. 정수 2의 방법들로 정수 4를 나타내는 방법

    • 1, 1, 2
    • 2, 2

  3. 정수 3의 방법들로 정수 4를 나타내는 방법

    • 1, 1, 1, 1
    • 1, 2, 1
    • 2, 1, 1
    • 3, 1

위 방법들은 문제에 나와있는 정수 4를 1, 2, 3의 합으로 나타내는 방법들과 동일하다.

답을 내기 위해 계속 자신보다 1, 2, 3이 작은 숫자를 나타내는 방법의 수을 참고해야 하기 때문에,
동적 계획법을 이용해 이전의 수들을 저장해놓고 이를 참고해 답을 내기 적합하다.

알고리즘

  1. 정수 1, 2, 3 각각을 1, 2, 3의 합으로 나타내는 방법의 수를 구해 메모한다.

  2. 정수 4부터 10까지 차례대로 1, 2, 3의 합으로 나타내는 방법의 수를 구해 메모한다.

    • 이때, 메모된 자신보다 1, 2, 3이 작은 숫자를 나타내는 방법의 수을 이용해 자신의 방법을 구한다.
  3. 입력된 숫자들 순서대로 메모를 참고해 방법의 수를 출력한다.

구현

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

//콘솔 입력 받는 변수
const input = [];

//memo[n] : 정수 n을 1, 2, 3의 합으로 나타내는 방법의 수
const memo = [...Array(11)];

const write = (num) => {
  memo[num] = memo[num - 1] + memo[num - 2] + memo[num - 3];
};

require('readline')
  .createInterface(process.stdin, process.stdout)
  .on('line', function (line) {
    input.push(line.trim());
  })
  .on('close', function () {
    //초기값 설정
    memo[1] = 1;
    memo[2] = 2;
    memo[3] = 4;

    for (let i = 4; i <= 10; i++) {
      //n이 11 미만이므로 10까지 방법의 수 저장
      write(i);
    }

    //테스트 케이스 총 수 입력 변수에서 제거
    input.splice(0, 1);
    //입력에 맞는 방법의 수 메모에서 출력
    input.forEach((numString) => {
      console.log(memo[Number(numString)]);
    });
  });

TABLE OF CONTENTS