백준 14500 테트로미노 C++

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

14500번: 테트로미노

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ14500_2.cpp

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

//
//  main.cpp
//  BJ14500
//
//  Created by Hwayeon on 2021/07/22.
//

#include <iostream>
using namespace std;

int N, M;
int paper[500][500] = {0,};
int answer = 0;

#테트로미노 표현
struct tetromino{
    pair<int, int> loc[4];
};
tetromino tm[19] = {
    //ㅡ
    {make_pair(0,0), make_pair(0,1), make_pair(0,2), make_pair(0,3)},
    //|
    {make_pair(0,0), make_pair(1,0), make_pair(2,0), make_pair(3,0)},
    //ㅁ
    {make_pair(0,0), make_pair(0,1), make_pair(1,0), make_pair(1,1)},
    //ㄴ
    {make_pair(0,0), make_pair(1,0), make_pair(2,0), make_pair(2,1)},
    {make_pair(0,0), make_pair(0,1), make_pair(0,2), make_pair(1,0)},
    {make_pair(0,0), make_pair(0,1), make_pair(1,1), make_pair(2,1)},
    {make_pair(1,0), make_pair(1,1), make_pair(1,2), make_pair(0,2)},
    {make_pair(2,0), make_pair(2,1), make_pair(1,1), make_pair(0,1)},
    {make_pair(0,0), make_pair(1,0), make_pair(1,1), make_pair(1,2)},
    {make_pair(0,0), make_pair(0,1), make_pair(1,0), make_pair(2,0)},
    {make_pair(0,0), make_pair(0,1), make_pair(0,2), make_pair(1,2)},
    //ㄹ
    {make_pair(0,0), make_pair(1,0), make_pair(1,1), make_pair(2,1)},
    {make_pair(0,1), make_pair(0,2), make_pair(1,1), make_pair(1,0)},
    {make_pair(0,1), make_pair(1,0), make_pair(1,1), make_pair(2,0)},
    {make_pair(0,0), make_pair(0,1), make_pair(1,1), make_pair(1,2)},
    //ㅜ
    {make_pair(0,0), make_pair(0,1), make_pair(0,2), make_pair(1,1)},
    //ㅓ
    {make_pair(1,0), make_pair(0,1), make_pair(1,1), make_pair(2,1)},
    //ㅗ
    {make_pair(0,1), make_pair(1,0), make_pair(1,1), make_pair(1,2)},
    //ㅏ
    {make_pair(0,0), make_pair(1,0), make_pair(1,1), make_pair(2,0)}
};

int main(int argc, const char * argv[]) {
    cin >> N >> M;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cin >> paper[i][j];
        }
    }
    //tetromino 선택
    for(int t=0; t<19; t++){
        //위치 선택
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                int sum = 0;
                int x, y = 0;
                //tetromino가 놓인 칸에 쓰인 수의 합
                for(int k=0; k<4; k++){
                    y = tm[t].loc[k].first+i;
                    x = tm[t].loc[k].second+j;
                    if(x<0||x>=M||y<0||y>=N){
                        sum = 0;
                        break;
                    }
                    sum += paper[y][x];
                }
                if(sum == 0) continue;
                if(answer < sum) answer = sum;
            }
        }
    }
    cout << answer << endl;
    return 0;
}

---

풀이 과정

풀이 시간 1시간 11분

NxM 종이에 테트로미노 중 하나를 어떻게, 어디에 놓을지를 결정하는 문제이다.

 

 먼저, 테트로미노의 종류는 5가지가 있는데 '어떻게 놓을지'라는 점에 초점을 기울여 보자.

문제에 제시된 부분을 살펴보면 '테트로미노는 종이의 한 칸에 테트로미노의 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.'

따라서, 5가지의 테트로미노를 표현할 때 회전이나 대칭을 하여 나오는 모든 경우의 수를 생각해 봐야 한다.

직접 종이에 그려가며 만들어 본 경우의 수는 다음과 같다.

 

-> 2가지

 

 

 

-> 1가지

 

 

 

 

 

-> 8가지

 

 

 

 

 

 

 

-> 4가지

 

 

 

 

 

 

-> 4가지

 

 

 

=> 총 19가지

 

 

 둘째, '어디에 놓을지'는 하나의 테트로미노가 놓인 종이의 칸에 쓰여 있는 수들의 합을 최대로 해야한다.

위에서 얘기한 테트로미노 종류 5가지를 각각 회전이나 대칭을 해서 나오는 모든 경우의 수를 종이의 (0, 0)부터 (N, M)까지 옮겨보면서 종이의 칸에 쓰여 있는 수들의 합을 비교해 나가면 된다.

 

//
//  main.cpp
//  BJ14500
//
//  Created by Hwayeon on 2021/07/22.
//

#include <iostream>
using namespace std;

int N, M;
int paper[500][500] = {0,};
int answer = 0;

#테트로미노 표현
struct tetromino{
    pair<int, int> loc[4];
};
tetromino tm[19] = {
    //ㅡ
    {make_pair(0,0), make_pair(0,1), make_pair(0,2), make_pair(0,3)},
    //|
    {make_pair(0,0), make_pair(1,0), make_pair(2,0), make_pair(3,0)},
    //ㅁ
    {make_pair(0,0), make_pair(0,1), make_pair(1,0), make_pair(1,1)},
    //ㄴ
    {make_pair(0,0), make_pair(1,0), make_pair(2,0), make_pair(2,1)},
    {make_pair(0,0), make_pair(0,1), make_pair(0,2), make_pair(1,0)},
    {make_pair(0,0), make_pair(0,1), make_pair(1,1), make_pair(2,1)},
    {make_pair(1,0), make_pair(1,1), make_pair(1,2), make_pair(0,2)},
    {make_pair(2,0), make_pair(2,1), make_pair(1,1), make_pair(0,1)},
    {make_pair(0,0), make_pair(1,0), make_pair(1,1), make_pair(1,2)},
    {make_pair(0,0), make_pair(0,1), make_pair(1,0), make_pair(2,0)},
    {make_pair(0,0), make_pair(0,1), make_pair(0,2), make_pair(1,2)},
    //ㄹ
    {make_pair(0,0), make_pair(1,0), make_pair(1,1), make_pair(2,1)},
    {make_pair(0,1), make_pair(0,2), make_pair(1,1), make_pair(1,0)},
    {make_pair(0,1), make_pair(1,0), make_pair(1,1), make_pair(2,0)},
    {make_pair(0,0), make_pair(0,1), make_pair(1,1), make_pair(1,2)},
    //ㅜ
    {make_pair(0,0), make_pair(0,1), make_pair(0,2), make_pair(1,1)},
    //ㅓ
    {make_pair(1,0), make_pair(0,1), make_pair(1,1), make_pair(2,1)},
    //ㅗ
    {make_pair(0,1), make_pair(1,0), make_pair(1,1), make_pair(1,2)},
    //ㅏ
    {make_pair(0,0), make_pair(1,0), make_pair(1,1), make_pair(2,0)}
};

int main(int argc, const char * argv[]) {
    cin >> N >> M;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cin >> paper[i][j];
        }
    }
    //tetromino 선택
    for(int t=0; t<19; t++){
        //위치 선택
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                int sum = 0;
                int x, y = 0;
                //tetromino가 놓인 칸에 쓰인 수의 합
                for(int k=0; k<4; k++){
                    y = tm[t].loc[k].first+i;
                    x = tm[t].loc[k].second+j;
                    if(x<0||x>=M||y<0||y>=N){
                        sum = 0;
                        break;
                    }
                    sum += paper[y][x];
                }
                if(sum == 0) continue;
                if(answer < sum) answer = sum;
            }
        }
    }
    cout << answer << endl;
    return 0;
}
#시간복잡도 = O(n^3), 공간복잡도 = O(n^2)