14500

백준 14500번

Link: 14500번: 테트로미노

---

문제 설명

최대 500*500의 지도 위에 블럭을 놓을 수 있는 모든 경우를 고려하여 블럭이 놓인 부분에 위치한 숫자 합의 최대값을 찾는 문제.

우선 블럭을 회전시키거나 대칭시켜보며 나올 수 있는 모든 경우를 생각해보았다.

다 해보니 꽤 많았는데, 19가지였다.

500*500짜리 지도에서 최악의 경우 500 * 500 * 19 = 4750000가지 경우를 전부 고려해봐야 하는데 이게 시간초과 안나고 가능할까? 라는 생각이 먼저 들었다.

처음에는 19가지 도형이 전부 들어갈 수 있는 최소한의 넓이인 4*4짜리 map을 따로 만들어 이걸로 맞춰볼 생각을 해봤는데, 이 안에서 나올 수 있는 19가지 도형의 위치 경우의 수를 구해보니 113가지가 되더라.

이건 아니다 싶어 결국 switch문 안에 19가지 경우를 전부 명시해서 넣고 3중 for문으로 돌렸다.

조건문이 19가지나 되다 보니 중간에 헷갈려서 조건 잘못쓴 경우도 있었고 계산식 잘못 넣은 경우도 있었다.

어찌어찌해서 다 잡아내고 돌려봤는데, 시간초과날줄 알았는데 잘 돌아가서 정답으로 나오더라.

DFS나 BFS처럼 알려진 방법 말고 이런 무식한 방법으로 풀리는 문제도 있구나 하는 생각이 들었다.

아마 시뮬레이션 문제를 풀게 된다면 이런 문제가 아닐까라는 생각도 들었고.

여튼 그리 깊게 생각하지 않아도 풀 수 있는 문제였다.

---

정답 코드

//
// Created by Keith_Lee on 12/02/2019.
//

#include <iostream>

using namespace std;

int N, M;
int map[500][500] = {0, };
int result = 0;

int max(int a, int b){
    return a < b ? b : a;
}

int main(){
    cin >> N >> M;

    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cin >> map[i][j];
        }
    }

    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            for(int shape=0; shape<19; shape++) {
                int sum = 0;

                switch (shape) {
                    case 0:
                        if(j+3 < M){
                            sum += map[i][j] + map[i][j+1] + map[i][j+2] + map[i][j+3];
                        }
                        break;
                    case 1:
                        if(i+3 < N){
                            sum += map[i][j] + map[i+1][j] + map[i+2][j] + map[i+3][j];
                        }
                        break;
                    case 2:
                        if(i+1 < N && j+1 < M){
                            sum += map[i][j] + map[i+1][j] + map[i][j+1] + map[i+1][j+1];
                        }
                        break;
                    case 3:
                        if(i+2 < N && j+1 < M){
                            sum += map[i][j] + map[i+1][j] + map[i+2][j] + map[i+2][j+1];
                        }
                        break;
                    case 4:
                        if(i+2 < N && j-1 >= 0){
                            sum += map[i][j] + map[i+1][j] + map[i+2][j] + map[i+2][j-1];
                        }
                        break;
                    case 5:
                        if(i+1 < N && j+2 < M){
                            sum += map[i][j] + map[i][j+1] + map[i][j+2] + map[i+1][j];
                        }
                        break;
                    case 6:
                        if(i+1 < N && j+2 < M){
                            sum += map[i][j] + map[i][j+1] + map[i][j+2] + map[i+1][j+2];
                        }
                        break;
                    case 7:
                        if(i+2 < N && j+1 < M){
                            sum += map[i][j] + map[i][j+1] + map[i+1][j+1] + map[i+2][j+1];
                        }
                        break;
                    case 8:
                        if(i+2 < N && j+1 < M){
                            sum += map[i][j] + map[i][j+1] + map[i+1][j] + map[i+2][j];
                        }
                        break;
                    case 9:
                        if(i-1 >= 0 && j+2 < M){
                            sum += map[i][j] + map[i][j+1] + map[i][j+2] + map[i-1][j+2];
                        }
                        break;
                    case 10:
                        if(i+1 < N && j+2 < M){
                            sum += map[i][j] + map[i+1][j] + map[i+1][j+1] + map[i+1][j+2];
                        }
                        break;
                    case 11:
                        if(i+2 < N && j+1 < M){
                            sum += map[i][j] + map[i+1][j] + map[i+1][j+1] + map[i+2][j+1];
                        }
                        break;
                    case 12:
                        if(i-1 >= 0 && j+2 < M){
                            sum += map[i][j] + map[i][j+1] + map[i-1][j+1] + map[i-1][j+2];
                        }
                        break;
                    case 13:
                        if(i+2 < N && j-1 >= 0){
                            sum += map[i][j] + map[i+1][j] + map[i+1][j-1] + map[i+2][j-1];
                        }
                        break;
                    case 14:
                        if(i+1 < N && j+2 < M){
                            sum += map[i][j] + map[i][j+1] + map[i+1][j+1] + map[i+1][j+2];
                        }
                        break;
                    case 15:
                        if(i+1 < N && j+2 < M){
                            sum += map[i][j] + map[i][j+1] + map[i][j+2] + map[i+1][j+1];
                        }
                        break;
                    case 16:
                        if(i+2 < N && i-1 >= 0 && j+1 < M){
                            sum += map[i][j] + map[i][j+1] + map[i+1][j+1] + map[i-1][j+1];
                        }
                        break;
                    case 17:
                        if(i-1 >= 0 && j+2 < M){
                            sum += map[i][j] + map[i][j+1] + map[i-1][j+1] + map[i][j+2];
                        }
                        break;
                    case 18:
                        if(i+2 < N && j+1 < M){
                            sum += map[i][j] + map[i+1][j] + map[i+2][j] + map[i+1][j+1];
                        }
                        break;
                }

                result = max(sum, result);
            }
        }
    }

    cout << result << '\n';

    return 0;
}

---