Gidhub BE Developer

[BOJ] 14500. 테트로미노

2018-10-16
goodGid

Problem

Problem URL : 테트로미노


[1] Answer Code (18. 10. 16)

#include<iostream>
#include<vector>
#include<algorithm>
#define p pair<int,int>
using namespace std;

int n,m;
int map[500][500];

/*
 (0,0)부터 시작하여 체크할 수 있는 범위를 제한
 n = 4
 m = 4라면
 ㅡ 모양의 크기는
 (0,0) 기준에서
 현재 크기에서 [ 0 , 3 ] 더한 값이다. (= p(0,3 )
 머리로 생각하면
 n은 0 ~ 3까지
 m은 0 ~ 0까지
 
 코드로 나타내면
 row_idx는 0 ~ 3(= n-0)
 col_idx는 0 ~ 1(= m-3)
 
 ㅜ 모양 같은 경우에는
 (0,0)에서 p(1,2)를 더해야한다.
 그러므로
 n은 0 ~ 3(= 4-1)
 m은 0 ~ 2(= 4-2)
 */
p range[] ={
    // 총 19개
    p(0,3), // ㅡ [1개]
    p(3,0), // ㅣ [1개]
    p(1,1), // ㅁ [1개]
    p(2,1), // ㅓ , ㅏ , ㄴㄱ  , L , ㄱ [5개] + L 반대모양 , ㄱ 좌우 반전 모양  , H 좌상 우하 빠진 모양
    p(1,2) // ㅗ, ㅜ , ㅢ- , ㅣ------ ( ---ㄱ 좌우 반대 모양 ), ㅡㅡㅡㅡㅡㅢ 모양 [5개] + ㄴ , ----ㄱ, ㄱㄴ
};

// 각 모양마다 i,j좌표에서 더해줘야하는 값
p chk[19][4] = {
    { p(0,0), p(0,1), p(0,2),p(0,3) }, // ㅣ
    { p(0,0), p(1,0), p(2,0),p(3,0) }, // ㅡ
    { p(0,0), p(0,1), p(1,0),p(1,1) }, // ㅁ
    
    { p(1,0), p(0,1), p(1,1),p(2,1) }, // ㅓ
    { p(0,0), p(1,0), p(2,0),p(1,1) }, // ㅏ
    { p(0,0), p(1,0), p(1,1),p(2,1) }, // ㄴㄱ
    { p(0,0), p(1,0), p(2,0),p(2,1) }, // L
    { p(0,0), p(0,1), p(1,1),p(2,1) }, // ㄱ
    
    { p(2,0), p(0,1), p(1,1),p(2,1) }, // L 반대모양
    { p(0,0), p(0,1), p(1,0),p(2,0) }, // ㄱ 좌우 반전 모양
    { p(1,0), p(2,0), p(0,1),p(1,1) }, // H 좌상 우하 빠진 모양
    
    
    { p(0,1), p(1,0), p(1,1),p(1,2) }, // ㅗ
    { p(0,0), p(0,1), p(0,2),p(1,1) }, // ㅜ
    { p(1,0), p(0,1), p(1,1),p(0,2) }, // ㅡ ㅣ -
    { p(0,0), p(0,1), p(0,2),p(1,0) }, // ㅣ------ ( ---ㄱ 좌우 반대  모양 )
    { p(1,0), p(1,1), p(1,2),p(0,2) }, // ㅡㅡㅡㅡㅡㅢ
    
    { p(0,0), p(1,0), p(1,1),p(1,2) }, // ㄴ
    { p(0,0), p(0,1), p(0,2),p(1,2) }, // ----ㄱ
    { p(0,0), p(0,1), p(1,1),p(1,2) } // ㄱㄴ
};


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            cin >> map[i][j];
    
    int ans = -1;
    
    for(int k=0; k<19; k++){
        p _range;
        if( k < 3 ) _range = range[k];
        else if( k < 11) _range = range[3];
        else _range = range[4];
        
        for(int i=0; i<n -_range.first; i++){
            for(int j=0; j<m -_range.second; j++){
                int sum = 0;
                for(int t=0; t<4; t++){
                    sum += map[ i + chk[k][t].first ][ j + chk[k][t].second ];
                }
                ans = ans < sum ? sum : ans;
            }
        }
    }
    
    cout << ans << endl;
    return 0;
}

Review

  • 삼성 역량 테스트 기출 문제

  • 정말 노가다로 풀었다.

  • 처음에 모양이 13개만 나오는지 알았는데 6개가 더 있었다. 그래서 총 19개 모양에 대해 구해주면 된다.


Recommend

Index