(C++) - 백준(BOJ) 14500번 : 테트로미노 답

www.acmicpc.net/problem/14500

14500번: 테트로미노

완전탐색(brute force)을 구현해보는 문제였습니다.

 

풀이방법 : 도형의 종류를 구분하고 이 도형을 구성하는 타일 값들의 합 중 최대값이 답입니다.

 

 도형 1. 2가지의 모양들 중 각 모양에 대한 타일들 합 최대값 반환

 

 

도형 2. 1가지 모양에 대한 타일들 합 반환

 

 

도형 3. 8가지 모양들 중 각 모양에 대한 타일들 합 최대값 반환

 

 

도형 4. 4가지 모양들 중 각 모양에 대한 타일들 합 최대값 반환

 

 

도형 5. 4가지 모양들 중 각 모양에 대한 타일들 합 최대값 반환

 

 도형1에서 도형5까지의 타일들 합의 최대를 구해주면 됩니다.

 

Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int n, m,ans;
int paper[501][501];

int getFirstShape(int i,int j){
    int tmp = 0;
    if(0 <= i && i < n && 0 <= j && j + 3 <m){
        tmp = max(tmp,paper[i][j]+paper[i][j+1]+paper[i][j+2] + paper[i][j+3]);
    }
    if(0 <= i && i + 3 < n && 0 <= j && j < m){
        tmp = max(tmp,paper[i][j]+paper[i+1][j]+paper[i+2][j] + paper[i+3][j]);
    }
    return tmp;
}

int getSecondShape(int i,int j){
    if(0 <= i && i + 1 < n && 0 <= j && j + 1 <m)
        return paper[i][j]+paper[i][j+1]+paper[i+1][j]+paper[i+1][j+1];
    return 0;
}

int getThirdShape(int i,int j) {
    int tmp = 0;
    if(0 <= i && i + 2 < n && 0 <= j && j + 1 < m)
        tmp = max(tmp,paper[i][j] + paper[i+1][j]+paper[i+2][j]+paper[i+2][j+1]);
    if(0 <= i && i + 2 < n && 0 <= j - 1 && j - 1 < m)
        tmp = max(tmp,paper[i][j] + paper[i+1][j]+paper[i+2][j]+paper[i+2][j-1]);
    if(0 <= i && i + 1 < n && 0 <= j && j + 2 < m)
        tmp = max(tmp,paper[i][j] + paper[i+1][j]+paper[i][j+1]+paper[i][j+2]);
    if(0 <= i && i + 1 < n && 0 <= j && j + 2 < m)
        tmp = max(tmp,paper[i][j] + paper[i+1][j]+paper[i+1][j+1]+paper[i+1][j+2]);
    if(0 <= i && i + 2 < n && 0 <= j && j + 1 < m)
        tmp = max(tmp,paper[i][j] + paper[i][j+1]+paper[i+1][j+1]+paper[i+2][j+1]);
    if(0 <= i && i + 2 < n && 0 <= j && j + 1 < m)
        tmp = max(tmp,paper[i][j] + paper[i+1][j]+paper[i+2][j]+paper[i][j+1]);
    if(0 <= i && i + 1 < n && 0 <= j - 2 && j < m)
        tmp = max(tmp,paper[i][j] + paper[i+1][j]+paper[i+1][j-1]+paper[i+1][j-2]);
    if(0 <= i && i + 1 < n && 0 <= j - 2 && j < m)
        tmp = max(tmp,paper[i][j] + paper[i][j-1]+paper[i][j-2]+paper[i+1][j]);
    return tmp;
}

int getForthShape(int i,int j){
    int tmp = 0;
    if(0 <= i && i + 2 < n && 0 <= j && j + 1 <m)    
        tmp = max(tmp,paper[i][j]+paper[i+1][j]+paper[i+1][j+1]+paper[i+2][j+1]);
    if(0 <= i - 1 && i < n && 0 <= j && j + 2 < m)
        tmp = max(tmp,paper[i][j]+paper[i][j+1]+paper[i-1][j+1]+paper[i-1][j+2]);
    if(0 <= i && i + 2 < n && 0 <= j - 1 && j < m)
        tmp = max(tmp,paper[i][j]+paper[i+1][j]+paper[i+1][j-1]+paper[i+2][j-1]);
    if(0 <= i && i + 1 < n && 0 <= j && j + 2 < m)
        tmp = max(tmp,paper[i][j]+paper[i][j+1]+paper[i+1][j+1]+paper[i+1][j+2]);
    return tmp;
}

int getFifthShape(int i, int j){
    int tmp = 0;

    if(0 <= i && i + 1 < n && 0 <= j && j + 2 < m)
        tmp = max(tmp,paper[i][j]+paper[i][j+1]+paper[i][j+2]+paper[i+1][j+1]);
    if(0 <= i && i + 2 < n && 0 <= j && j + 1 < m)  
        tmp = max(tmp,paper[i][j]+paper[i+1][j]+paper[i+1][j+1]+paper[i+2][j]);
    if(0 <= i - 1 && i < n && 0 <= j && j + 2 < m)
        tmp = max(tmp,paper[i][j]+paper[i][j+1]+paper[i-1][j+1]+paper[i][j+2]);
    if(0 <= i && i + 2 < n && 0 <= j - 1 && j < m)
        tmp = max(tmp,paper[i][j]+paper[i+1][j]+paper[i+1][j-1]+paper[i+2][j]);
    return tmp;
}

int tetromino(int i,int j) {
    int answer = 0;
    answer = max(answer,getFirstShape(i,j));
    answer = max(answer,getSecondShape(i,j));
    answer = max(answer,getThirdShape(i,j));
    answer = max(answer,getForthShape(i,j));
    answer = max(answer,getFifthShape(i,j));
    return answer;
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> paper[i][j];

    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            ans = max(ans,tetromino(i,j));
    cout << ans <<'\n';
}