다리 놓기

문제

• 백준 1010번 - 다리 놓기

언어

• JavaScript

문제 풀이 step 1

• dp[n][m] = 서쪽 사이트의 개수가 n, 동쪽 사이트의 개수가 m일 때 놓을 수 있는 다리의 최대 개수
• DP의 특징인 작은 문제의 해답으로부터 큰 문제의 해답을 찾는다를 이용합니다.
• 서쪽이 n, 동쪽이 m인 경우, 하나씩 그려보며 경우의 수를 찾아보겠습니다.
  • 서쪽에서 가장 위의 사이트(0 번)를 동쪽에서 가장 위의 사이트(0 번)와 연결할 때
    • 밑에는 서쪽이 n - 1, 동쪽이 m - 1인 경우가 됩니다. 즉 dp[n - 1][m - 1]입니다.
  • 서쪽에서 가장 위의 사이트(0 번)를 동쪽에서 그 다음 사이트(1 번)와 연결할 때
    • 밑에는 서쪽이 n - 1, 동쪽이 m - 2인 경우가 됩니다. 즉 dp[n - 1][m - 2]입니다.
  • …
  • 서쪽에서 가장 위의 사이트(0 번)를 동쪽에서 밑에서 n 번쨰인 사이트와 연결할 때 (서쪽에서 맨 위의 사이트를 제외한 나머지 n - 1개의 사이트를 모두 연결할 수 있는 마지막 경우)
    • 밑에는 서쪽이 n - 1, 동쪽이 n - 1인 경우가 됩니다. 즉, dp[n - 1][n - 1]입니다.
• 위에서 우리가 고려한 모든 경우의 수를 더하면 dp[n][m]을 구할 수 있습니다.
• 점화식은 dp[n][m] = dp[n - 1][m - 1] + dp[n - 1][m - 2] + … + dp[n - 1][n - 1]

후기

• 작은 단위의 경우만 생각하면 지역적인 답이 나올 수 있기 때문에 큰 단위의 경우도 생각해봐야 합니다.
• n이 3인 경우만 생각해보고 풀었다가 정답이 안나와서 문제의 그림을 보고 n이 4인 경우를 생각해보니 너무 좁게 생각했다는 것을 깨달았습니다.
• 다시 풀어보는데 조금 어려움을 겪었습니다. DP 문제는 작은 문제의 해답이 큰 문제의 해답을 구하는 사용될 수 있다는 것을 명심해야겠습니다.

소스 코드

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

const solution = (input) => {
	let T = parseInt(input[0]);
	const testCase = input.slice(1, T + 1);

	const dp = Array.from({length: 30}, () => []);
	// base
	dp[1] = Array.from({length: 30}, (v, i) => i);
	for (let i = 2; i < 30; i++) {
		// n === m 인 경우
		dp[i][i] = 1;

		// n < m 인 경우
		for (let j = i + 1; j < 30; j++) {
			let temp = 0;
			for (let n = i - 1, m = j - 1; m >= n; m--) {
				temp += dp[n][m];
			}

			dp[i][j] = temp;
		}
	}

	let res = "";
	let index = 0;
	while (T-- > 0) {
		const [n, m] = testCase[index++].split(" ").map(Number);
		res += `${dp[n][m]}\n`;
	}

	return res;
};

console.log(solution(input));