신나는 함수 실행

문제

• 백준 9184번 - 신나는 함수 실행

언어

• JavaScript

순서도

1. 3 차원 형식의 dp 배열 생성하기
2. 문제에서 주어진 조건에 맞는 재귀함수 w(a, b, c) 구현
   • 단, 재귀함수 구현시 dp 배열을 이용한 메모이제이션을 통해서 중복 호출 제거

문제 풀이 step 1

문제 풀이 step 2

• 위와 같은 재귀함수 w(a, b, c) 를 구현하는 문제입니다.
• 단, 단순히 재귀함수로 구현할 경우, 값을 구하는 과정 속에서 중복된 재귀호출이 상당히 많이 발생하기 때문에 메모이제이션을 통해서 중복 호출을 제거해줍니다.
• 재귀함수의 내부 로직은 위의 조건들 그대로 구현하면 됩니다.
  • 이에 추가로, 값을 return 할 때 별도의 배열에 값을 저장해주는 로직을 추가해줍니다.
    • return (dp[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c));
    • return (dp[a][b][c] = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1));
  • 또한 재귀호출을 통해서 구하려는 값이 이미 배열에 저장되어 있다면, 배열에 저장된 값을 return 하는 로직을 추가해줍니다.
    • if (dp[a][b][c] !== 0) return dp[a][b][c];
• 위와 같은 메모이제이션 로직을 추가한 재귀함수 w(a, b, c) 를 구현하면 정답입니다.
• 추가 설명은 주석으로 작성하겠습니다.

후기

• 메모이제이션의 용도가 값의 저장을 통해서 중복된 재귀호출을 제거하는 역할이라는 것은 알고 있었지만, 실제로 재귀함수와 함께 사용해본 것은 처음이었습니다.
• 방법은 함수 속에서 또 함수를 return 할 때, 별도의 배열에 결과값을 담음과 동시에 return 하면 되었습니다.
• return (a = b); 가 성립한다는 것을 다시 한 번 복습할 수 있었습니다.

소스 코드

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

// 메모이제이션을 위한 dp 배열 생성
const dp = Array.from({length: 21}, () =>
	Array.from({length: 21}, () => Array(21).fill(0))
);

// 문제에서 주어진 조건에 따라서 재귀함수 w(a, b, c) 구현
const w = (a, b, c) => {
	if (a <= 0 || b <= 0 || c <= 0) return 1;

	if (a > 20 || b > 20 || c > 20) {
		return (dp[20][20][20] = w(20, 20, 20));
	}

	// 메모이제이션 로직 추가
	if (dp[a][b][c] !== 0) return dp[a][b][c];

	// 메모이제이션 로직 추가
	if (a < b && b < c) {
		return (dp[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c));
	}

	// 메모이제이션 로직 추가
	return (dp[a][b][c] =
		w(a - 1, b, c) +
		w(a - 1, b - 1, c) +
		w(a - 1, b, c - 1) -
		w(a - 1, b - 1, c - 1));
};

const solution = (input) => {
	let res = "";
	let index = 0;
	while (true) {
		const [a, b, c] = input[index++].split(" ").map(Number);
		if (a === -1 && b === -1 && c === -1) break;

		res += `w(${a}, ${b}, ${c}) = ${w(a, b, c)}\n`;
	}

	return res;
};

console.log(solution(input));