백준 알고리즘 9095번 1, 2, 3 더하기

문제 링크

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

---

문제 설명

문제

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

---

문제 풀이

이 문제는 답이 나오는 규칙을 먼저 찾아야한다.
규칙을 보기 위해 1, 2, 3, 4의 답들을 구해 보겠다.

1

• 1

따라서 답은 1.

2

• 1 + 1
• 2

답은 2.

3

• 1 + 1 + 1
• 1 + 2
• 2 + 1
• 3

답은 4.

4

• 1 + 1 + 1 + 1
• 1 + 1 + 2
• 1 + 2 + 1
• 2 + 1 + 1
• 1 + 3
• 3 + 1
• 2 + 2

답은 7이다.

4의 답은 3, 2, 1의 답을 합친 것과 같다. 그 이유는 4의 답의 구성은 3의 답 구성에 1을 더한 것, 2의 답 구성에 2를 더한 것, 1의 답 구성에 3을 더한 것들로 구성되어 있기 때문이다.

다시 한번 4의 답 구성을 보자.

• 1 + ( 1 + 1 + 1 )
• 1 + ( 1 + 2 )
• 1 + ( 2 + 1 )
• 1 + ( 3 )
• 2 + ( 1 + 1 )
• 2 + ( 2 )
• 3 + ( 1 )

그렇기 때문에 입력값 중 최대값까지의 답을 구하고서 순서에 맞게 출력값을 붙여주면 된다.

코드

// 제출용 input
let input = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n')
  .splice(1);

// 실행용
// const input = '3\n4\n7\n10'.split('\n').splice(1);
//ansArr[n] : 정수 n을 1, 2, 3의 합으로 나타내는 방법의 수
const ansArr = Array(10);
let result = '';

//초기값 설정
ansArr[0] = 1;
ansArr[1] = 2;
ansArr[2] = 4;

for (let i = 3; i < 10; i++) {
  //n이 10 이하이므로 10까지 방법의 수 저장
  ansArr[i] = ansArr[i - 1] + ansArr[i - 2] + ansArr[i - 3];
}
//입력에 맞는 방법의 수 메모에서 출력
input.forEach((value) => {
  result += `${ansArr[value * 1 - 1]}\n`;
});

console.log(result);