테트로미노

문제

언어

  • JavaScript

순서도

  1. N x M 크기의 격자의 모든 요소를 순회하며,
  2. 각각의 테트로미노를 놓아보고, 테트로미노 안의 수들의 합을 다 구해보고,
  3. 그 중에서 최댓값을 출력

문제 풀이 step 1

  • N x M 크기의 격자가 있을 때, 총 5 가지의 테트로미노를 회전이나 대칭을 시키며 놓아보고, 놓았을 때의 테트로미노 안의 수들을 더한 값들 중에서 최댓값을 찾는 문제입니다.
  • 브루트포스 형식의 문제로 모든 가능한 경우를 다 검사해보는 문제입니다.
  • 특별한 로직은 크게 필요없고, 약간의 노가다 형식으로 5 개의 테트로미노로 만들 수 있는 모든 경우를 만들어 보면 됩니다.
  • 총 19 가지의 경우가 있습니다.
    1. ㅡ 모양의 도형 : 2 가지
    2. 정사각 모양의 도형 : 1 가지
    3. ㄴ 모양의 도형 : 8 가지
    4. 지그재그 모양의 도형 : 4 가지
    5. ㅜ 모양의 도형 : 4 가지
  • 이렇게 각 경우를 만들어보고, 그 때의 총합 중에서 최댓값을 출력하면 정답입니다.
  • 추가 설명은 주석으로 작성하겠습니다.

소스 코드 1

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

const solution = (input) => {
	const [n, m] = input[0].split(" ").map(Number);
	const arr = input.slice(1).map((v) => v.split(" ").map(Number));

	let max = 0;
	let num = 0;
	// n x m 크기의 격자의 모든 요소를 순회하며,
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < m; j++) {
			// 1. `ㅡ` 모양의 도형 : 2 가지
			if (j + 3 < m) {
				num = arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i][j + 3];
				max = Math.max(max, num);
			}

			if (i + 3 < n) {
				num = arr[i][j] + arr[i + 1][j] + arr[i + 2][j] + arr[i + 3][j];
				max = Math.max(max, num);
			}

			// 2. 정사각 모양의 도형 : 1 가지
			if (i + 1 < n && j + 1 < m) {
				num = arr[i][j] + arr[i + 1][j] + arr[i][j + 1] + arr[i + 1][j + 1];
				max = Math.max(max, num);
			}

			// 3. `ㄴ` 모양의 도형 : 8 가지
			if (i + 2 < n && j + 1 < m) {
				num = arr[i][j] + arr[i + 1][j] + arr[i + 2][j] + arr[i + 2][j + 1];
				max = Math.max(max, num);
			}

			if (i + 1 < n && j + 2 < m) {
				num =
					arr[i + 1][j] + arr[i + 1][j + 1] + arr[i + 1][j + 2] + arr[i][j + 2];
				max = Math.max(max, num);
			}

			if (i + 2 < n && j + 1 < m) {
				num = arr[i][j] + arr[i][j + 1] + arr[i + 1][j + 1] + arr[i + 2][j + 1];
				max = Math.max(max, num);
			}

			if (i + 1 < n && j + 2 < m) {
				num = arr[i][j] + arr[i + 1][j] + arr[i][j + 1] + arr[i][j + 2];
				max = Math.max(max, num);
			}

			if (i + 2 < n && j + 1 < m) {
				num =
					arr[i + 2][j] + arr[i][j + 1] + arr[i + 1][j + 1] + arr[i + 2][j + 1];
				max = Math.max(max, num);
			}

			if (i + 1 < n && j + 2 < m) {
				num = arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i + 1][j + 2];
				max = Math.max(max, num);
			}

			if (i + 2 < n && j + 1 < m) {
				num = arr[i][j] + arr[i][j + 1] + arr[i + 1][j] + arr[i + 2][j];
				max = Math.max(max, num);
			}

			if (i + 1 < n && j + 2 < m) {
				num = arr[i][j] + arr[i + 1][j] + arr[i + 1][j + 1] + arr[i + 1][j + 2];
				max = Math.max(max, num);
			}

			// 4. 지그재그 모양의 도형 : 4 가지
			if (i + 2 < n && j + 1 < m) {
				num = arr[i][j] + arr[i + 1][j] + arr[i + 1][j + 1] + arr[i + 2][j + 1];
				max = Math.max(max, num);
			}

			if (i + 1 < n && j + 2 < m) {
				num = arr[i + 1][j] + arr[i][j + 1] + arr[i + 1][j + 1] + arr[i][j + 2];
				max = Math.max(max, num);
			}

			if (i + 2 < n && j + 1 < m) {
				num = arr[i][j + 1] + arr[i + 1][j] + arr[i + 1][j + 1] + arr[i + 2][j];
				max = Math.max(max, num);
			}

			if (i + 1 < n && j + 2 < m) {
				num = arr[i][j] + arr[i][j + 1] + arr[i + 1][j + 1] + arr[i + 1][j + 2];
				max = Math.max(max, num);
			}

			// 5. `ㅜ` 모양의 도형 : 4 가지
			if (i + 1 < n && j + 2 < m) {
				num = arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i + 1][j + 1];
				max = Math.max(max, num);
			}

			if (i + 2 < n && j + 1 < m) {
				num = arr[i][j] + arr[i + 1][j] + arr[i + 2][j] + arr[i + 1][j + 1];
				max = Math.max(max, num);
			}

			if (i + 1 < n && j + 2 < m) {
				num =
					arr[i + 1][j] + arr[i][j + 1] + arr[i + 1][j + 1] + arr[i + 1][j + 2];
				max = Math.max(max, num);
			}

			if (i + 2 < n && j + 1 < m) {
				num =
					arr[i + 1][j] + arr[i][j + 1] + arr[i + 1][j + 1] + arr[i + 2][j + 1];
				max = Math.max(max, num);
			}
		}
	}

	// 최댓값 출력
	return max;
};

console.log(solution(input));