[백준] 9095

1, 2, 3 더하기

문제

정수 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은 양수이며 11보다 작다.

출력

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

풀이

const onetwothree = () => {
  let [n, ...input] = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split("\n")
    .map(Number);
  const max = Math.max(...input);
  let arr = Array.from({ length: max + 1 }, (v) => 0);
  let ans = [];
  (arr[1] = 1), (arr[2] = 2), (arr[3] = 4);
  for (let i = 4; i <= max; i++) arr[i] = arr[i - 1] + arr[i - 2] + arr[i - 3];
  for (let i of input) ans.push(arr[i]);
  console.log(ans.join("\n"));
};

onetwothree();

반성회

테이블 정의하기

D[N] = “N을 1, 2, 3의 합으로 나타내는 방법의 수”

점화식 찾기

• D[1] = 1개
  • 1
• D[2] = 2개
  • 1 + 1
  • 2
• D[3] = 4개
  • 1 + 1 + 1
  • 1 + 2
  • 2 + 1
  • 3
• D[4] =
  • 1 + 1 + 1 + 1
  • 1 + 1 + 2
  • 1 + 2 + 1
  • 1 + 3
  • 2 + 1 + 1
  • 2 + 2
  • 3 + 1

첫 번째 수가 1일 때의 개수는, 나머지 수의 합이 3이므로 3을 만드는 경우의 수와 같다 = D[3] = 4개

첫 번째 수가 2일 때의 개수는, 나머지 수의 합이 2이므로 2를 만드는 경우의 수와 같다 = D[2] = 2개

첫 번째 수가 3일 때의 개수는, 나머지 수의 합이 1이므로 1을 만드는 경우의 수와 같다 = D[1] = 1개

마찬가지로, D[5]는

• 첫 번째 수가 1일 때, 나머지 수의 합이 4이므로 4를 만드는 경우의 수와 같을 것 (D[4])
• 첫 번째 수가 2일 때, 나머지 수의 합이 3이므로 3을 만드는 경우의 수와 같을 것 (D[3])
• 첫 번째 수가 3일 때 나머지 수의 합이 2이므로 2를 만드는 경우의 수와 같을 것 (D[2])

결국 D[5] = D[4] + D[3] + D[2]

따라서 D[K]는

• 첫 번째 수가 1일 때, 나머지 수의 합이 K - 1이므로 K - 1을 만드는 경우의 수와 같다 = D[K - 1]
• 첫 번째 수가 2일 때, 나머지 수의 합이 K - 2이므로 K - 2를 만드는 경우의 수와 같다 = D[K - 2]
• 첫 번째 수가 3일 때, 나머지 수의 합이 K - 3이므로 K - 3을 만드는 경우의 수와 같다 = D[K - 3]

결국 D[K] = D[K - 1] + D[K - 2] + D[K - 3]

초기값 정하기

위 점화식으로 풀 수 있는 K의 최소값이 4이므로, 적어도 D[1], D[2], D[3]의 값을 알고 있어야 나머지 값을 구할 수 있다

D[1], D[2], D[3] 을 초기화하자

풀기

먼저 입력으로 들어온 수들 중 가장 큰 수를 찾고, 이를 마지막 인덱스로 갖는 (길이: M + 1) DP 배열을 선언한다

D[1], D[2], D[3] 을 초기화하고, i = 4부터 입력 최대값까지 반복문을 통해 모든 경우의 수를 배열에 저장한다

마지막엔 입력값들 각각에 대하여 DP 배열에 저장한 경우의 수를 가져오고, 출력한다