[백준/C++] 테트리스 (No. 4920)

문제

문제 설명

 

 

 

풀이

 

[문제 풀이]

 

이 문제를 처음 봤을 때 90도 회전을 구현 해야하나 고민했지만, 그럴 필요가 없다.

왜냐하면 테트리스 조각의 모양은 정해져 있기 때문에 각 조각들을 회전시킨 모양을 포함해 총 13가지의 경우만 계산하면 되기 때문이다.

 

그러므로 테트리스 조각 중 한 점을 선택하고 그 점을 기준으로 다른 조각들의 좌표를 미리 배열로 저장해서 만들어서 풀면 쉽게 풀 수 있다.

위 그림처럼 정사각형 모양의 테트리스 조각인 경우 (0, 0) 위치를 기준으로 다른 조각들은 (0, 1), (1, 0), (1, 1)에 위치하게 된다. 

 

이제 조각의 좌표를 만들었으면, 테트리스 조각이 들어갈 수 있는지 NxN 판에 대해 한 점씩 계산해보고 그 중 최댓값을 출력하면 되는 구현 문제다.

 

[아이디어 정리]

1. 테트리스 조각의 경우의 수가 정해져 있고, 작기 때문에 좌표를 미리 계산해서 배열로 만들어 둔다.
2. for문으로 NxN판의 각 좌표에 대해 테트리스 조각이 들어갈 수 있는지를 판단하고, 들어갈 수 있다면 그때 판의 수의 합을 비교하며 최댓값을 구한다.

 

 

Code1 (2차원 DP)

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
using namespace std;

// 테트리스 조각 좌표
int dx[13][4] = { {1,2,3},{0,0,0},{1,1,2 },{0,-1,-1},{1,2,2},{0,0,-1},{0,1,2},{1,0,0},{1,1,2},{0,0,-1},{-1,0,1},{0,0,1},{0,1,1} };
int dy[13][4] = { {0,0,0},{1,2,3},{0,1,1 },{1,1,2},	{0,0,1}, {1,2,2},{1,1,1},{0,1,2},{0,1,0},{1,2,1},{1,1,1},{1,2,1} ,{1,0,1} };

void calc(int &ans, int N, int x, int y, vector<vector<int>>&DM) {
	int ny, nx, dv;
	bool flag;
	for (int i = 0; i < 13; i++) {
		dv = DM[y][x];
		flag = true;
		for (int j = 0; j < 3; j++) {
			ny = y + dy[i][j];
			nx = x + dx[i][j];
			if (ny >= 0 && ny < N && nx >= 0 && nx < N) {
				dv += DM[ny][nx];
			}
			else {
				flag = false;
				break;
			}
		}
		if (flag) {
			ans = max(ans, dv);
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int tc = 1;
	while(true){
		int N;
		cin >> N;
		int ans = -4000000;
		if (N == 0) {
			return 0;
		}
		vector<vector<int>> DM(N, vector<int>(N + 1, 0));
		for (int i=0; i<N; i++){
			for (int j = 0; j < N; j++) {
				cin >> DM[i][j];
			}
		}



		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				calc(ans, N, i, j, DM);
			}
		}

		cout << tc << ". " << ans << "\n";
		tc++;

	}

	return 0;
}

 

 

---

 

새해 기념으로 오랜만에 알고리즘 문제를 풀었다...

그런데 최근에 매일 Java, JSP, JS, XML만 보다가 C++을 보니 vector 초기화랑 선언을 어떻게 했는지도 기억이 잘 안났다;

 

최근 취미(?)들이 많아져서 알고리즘을 풀 일은 없을거 같다.. 바쁘군 바빠...

 

https://www.acmicpc.net/problem/4920