[백준][삼성 SW 역량 테스트][Gold 5][C++] 14500 테트로미노

문제

백준 삼성 SW 역량 테스트 기출 문제 - 14500 테트로미노 (Gold 5)

14500번: 테트로미노

 

---

문제 풀이

접근 방식

아래의 테트로미노 중 하나를 회전하거나 대칭하여 주어진 종이에 놓았을 때,

놓인 칸에 쓰인 수들의 합의 최댓값을 구하는 문제이다.

 

테트로미노

 

우선, 각 테트로미노들을 회전하거나 대칭한 모양대로 탐색을 수행해야하기 때문에,

총 19개의 테트로미노들을 다음과 같이 구현하였다.

int dir[5][2] = { {-1,0},{0,1},{1,0},{0,-1},{-1,1} };
int tetromino[19][3] = {{ 1,1,1 }, { 2,2,2 }, { 1,2,3 }, { 2,2,1 }, { 0,1,1 },
			{ 1,1,0 }, { 1,2,2 }, { 1,0,0 }, { 2,1,1 }, { 3,2,2 },
			{ 1,1,2 }, { 2,1,2 }, { 1,0,1 }, { 2,3,2 }, { 1,2,1 }, 
			{ 1,2,4 }, { 4,2,2 }, { 4,2,1 }, { 2,2,4 }};

 

그 후, 완전 탐색으로 모든 칸에 모든 종류의 테트로미노를 놓아보며 최댓값을 구해주었다.

 

---

풀이 코드 - C++

#include <iostream>
#include <vector>
using namespace std;

int dir[5][2] = { {-1,0},{0,1},{1,0},{0,-1},{-1,1} };
int tetromino[19][3] = {{ 1,1,1 }, { 2,2,2 }, { 1,2,3 }, { 2,2,1 }, { 0,1,1 },
			{ 1,1,0 }, { 1,2,2 }, { 1,0,0 }, { 2,1,1 }, { 3,2,2 },
			{ 1,1,2 }, { 2,1,2 }, { 1,0,1 }, { 2,3,2 }, { 1,2,1 }, 
			{ 1,2,4 }, { 4,2,2 }, { 4,2,1 }, { 2,2,4 }};

int main() {
	// 입력 받기
	int N, M;
	cin >> N >> M;
	vector<vector<int>> map(N, vector<int>(M));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}

	int MAX = 0;
	int x, y, sum;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			for (int k = 0; k < 19; k++) {
				x = i; y = j;
				sum = map[x][y];
				for (int l = 0; l < 3; l++) {
					int nx = x + dir[tetromino[k][l]][0];
					int ny = y + dir[tetromino[k][l]][1];
					if (nx < 0 || nx >= N || ny < 0 || ny >= M) break;
					x = nx; y = ny;
					sum += map[x][y];
				}
				if (sum > MAX) MAX = sum;
			}
		}
	}
	cout << MAX;
}

실행 결과

실행 결과 : 통과 (88ms)