14500 테트로미노

테트로미노 (14500)

 

풀이코드

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
// 14500 테트로미노
const int MAX = 1000000;

// 19가지 테트로미노. 기준점을 제외한 나머지 3칸의 x,y 좌표를 가진 block 배열
int block[19][3][2] = {
    {{0,1}, {0,2}, {0,3}},
    {{1,0}, {2,0}, {3,0}},
    {{1,0}, {1,1}, {1,2}},
    {{0,1}, {1,0}, {2,0}},
    {{0,1}, {0,2}, {1,2}},
    {{1,0}, {2,0}, {2,-1}},
    {{0,1}, {0,2}, {-1,2}},
    {{1,0}, {2,0}, {2,1}},
    {{0,1}, {0,2}, {1,0}},
    {{0,1}, {1,1}, {2,1}},
    {{0,1}, {1,0}, {1,1}},
    {{0,1}, {-1,1}, {-1,2}},
    {{1,0}, {1,1}, {2,1}},
    {{0,1}, {1,1}, {1,2}},
    {{1,0}, {1,-1}, {2,-1}},
    {{0,1}, {0,2}, {-1,1}},
    {{0,1}, {0,2}, {1,1}},
    {{1,0}, {2,0}, {1,1}},
    {{1,0}, {2,0}, {1,-1}},
};

int board[500][500];
int N, M;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
	cin >> N >> M;
	
	for(int i = 0; i < N; i++)
		for(int j = 0; j < M ; j++)
			cin >> board[i][j];
			
	int maxSum = -1;
	
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M ; j++){
			// 현재 기준점 i,j 에 대해서 19가지 테트로미노를 모두 시험해본다.
			for(int tetro = 0; tetro < 19; tetro++){
				int sum = board[i][j];
				bool flag = true;
				for(int k = 0; k < 3; k++){
					int x = i + block[tetro][k][0];
					int y = j + block[tetro][k][1];
					
					if(x < 0 || x >= N || y < 0 || y >= M) {
						flag = false;
						break;
					}
					
					sum += board[x][y];
				}
				if(flag && maxSum < sum){
					maxSum = sum;
				}
			}
			
		}
	}
		
	cout << maxSum << '\n';
	
}

 

해설

---

적용한 레시피 / 방법론 + 접근법

- 주먹구구식 분석. 각 19가지의 테트로미노를 모두 놓아본다고 생각하였을 때, 1억을 절대 넘지 못한다. 브루트 포스로 시도할 이유가 생김.

풀이

- 5가지 테트로미노를 돌리고 뒤집어서 만들 수 있는 테트로미노는 19가지 이다.

- 각각의 테트로미노를, 임의의 기준점 ( 왼쪽 위 꼭짓점 ) 을 잡아 좌표 상으로 표시한다. (block 배열)

- 범위에 주의하며 모든 테트로미노를 모든 좌표에 놓아본다.

- 각 테트로미노 모양 당 sum 을 계산하여 maxSum 을 구한다.

 

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

- 순식간에 푼 문제였으나 오답이 나왔다. 한 번에 정답이 나오는 적이 없는 듯 하다. 항상 사소한 것에서 실수가 발생했다.

이번의 경우에는 기준점 (현재 좌표) 를 더하지 않아서 발생한 문제였다. 이러한 상수 오타는 아무도 잡아주지 못하니 집중하며 풀도록 하자. 

프로그램을 구성할 논리를 구성할 때, 철저히 구성해야 하며, 그 논리에만 따라서 프로그램을 작성하자.

테트로미노를 string 으로 직접 생성하여 프로그램 내에서 돌리고 뒤집은 풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
vector<vector<string>> blocks = {
    {"1111"},
    {"11",
     "11"},
    {"10",
     "10",
     "11"},
    {"10",
     "11",
     "01"},
    {"111",
     "010"}
};
vector<string> mirror(vector<string> &b) {
    vector<string> ans(b.size());
    for (int i=0; i<b.size(); i++) {
        string temp(b[i]);
        reverse(temp.begin(), temp.end());
        ans[i] = temp;
    }
    return ans;
}
vector<string> rotate(vector<string> &b) {
    vector<string> ans(b[0].size());
    for (int j=0; j<b[0].size(); j++) {
        for (int i=(int)b.size()-1; i>=0; i--) {
            ans[j] += b[i][j];
        }
    }
    return ans;
}
int calc(vector<vector<int>> &a, vector<string> &b, int x, int y) {
    int n = a.size();
    int m = a[0].size();
    int sum = 0;
    for (int i=0; i<b.size(); i++) {
        for (int j=0; j<b[0].size(); j++) {
            if (b[i][j] == '0') continue;
            int nx = x+i;
            int ny = y+j;
            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                sum += a[nx][ny];
            } else {
                return -1;
            }
        }
    }
    return sum;
}
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            cin >> a[i][j];
        }
    }
    int ans = 0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            for (auto &block : blocks) {
                vector<string> b(block);
                for (int mir=0; mir<2; mir++) {
                    for (int rot=0; rot<4; rot++) {
                        int cur = calc(a, b, i, j);
                        if (cur != -1 && ans < cur) {
                            ans = cur;
                        }
                        b = rotate(b);
                    }
                    b = mirror(b);
                }
            }
        }
    }
    cout << ans << '\n';
    return 0;
}