1, 2, 3 더하기

문제

• 백준 9095번 - 1, 2, 3 더하기

언어

• JavaScript

재귀

• 구조
  1. 불가능 한 경우
     • 재귀를 진행하다가 더이상 호출을 할 수 없는 경우 또는 더이상의 호출이 의미가 없는 경우
     • 후자는 백트래킹에 이용이 될 것입니다. 즉, 의미없는 호출을 제거함으로 속도를 향상시키는 것입니다.
  2. 정답을 찾는 경우
     • 호출을 진행하다가 정답을 찾았기 때문에 더이상 호출을 하지 않는 경우
  3. 다음 경우 호출
     • 정답을 찾기 위해서 다음 경우를 호출하는 경우
     • 보통 다음 경우를 호춣할 때 문제의 크기가 작아지는 방향으로 재귀 호출을 합니다.
• 보통 재귀 함수는 위의 3 가지 경우를 가진 구조로 이루어져있습니다.

문제 풀이 step 1

• 백준 9095번 - 1, 2, 3 더하기 풀이 에서 Dynamic Programming 기법으로 풀었는데 이번에는 재귀를 이용해서 풀었습니다.
• Dynamic Programming 기법의 풀이에서는 메모이제이션을 통해서 이전 단계에서 호출한 값은 다시 호출하지 않는 방식으로 풀었습니다.
• Recursion 기법의 풀이에서는 메모이제이션 없이 작은 단위로의 재귀 호출을 통해서 풀 수 있습니다.

소스 코드 1

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

const rec = (n) => {
	if (n === 0) return 1;
	if (n === 1) return 1;
	if (n === 2) return 2;

	if (n > 2) return rec(n - 1) + rec(n - 2) + rec(n - 3);
};

const solution = (input) => {
	let t = parseInt(input[0]);
	let index = 1;
	let res = "";

	while (t-- > 0) {
		const n = parseInt(input[index++]);

		res += rec(n) + "\n";
	}

	return res;
};

console.log(solution(input));