백준 알고리즘 14500

 

입력 : 종이사이즈 N*M, 종이 위에 적힌 수

출력 : 테트로미노와 닿은 수를 합한 수들 중 가장 큰 수

 

풀이

1. 테트로미노는 5개이지만 회전, 대칭이 가능하기 때문에 회전했을 때와 대칭했을 때의 모양도 각각 만들어둔다.
    -> 테트로미노는 왼쪽 위를 기준으로 만든다.
        ex) ---- : (0,0), (0,1), (0,2), (0,3)

2. 한 테트로미노의 기준점(왼쪽 맨위)을 종이 위의 모든 칸에 적용해 수를 합해본다.
    -> 종이를 벗어날 경우엔 0

3. 2번에서 구한 값들 중 가장 큰 수를 출력한다.

 

소스코드

#include <iostream>
using namespace std;
 
int tetromino[19][4][2] = {
    // figure 1
    { {0,0}, {0,1}, {0,2}, {0,3} },
    { {0,0}, {1,0}, {2,0}, {3,0} },
    // figure 2
    { {0,0}, {0,1}, {1,0}, {1,1} },
    // figure 3
    { {0,0}, {1,0}, {2,0}, {2,1} },
    { {1,0}, {1,1}, {1,2}, {0,2} },
    { {0,0}, {0,1}, {1,1}, {2,1} },
    { {0,0}, {1,0}, {0,1}, {0,2} },
    { {0,1}, {1,1}, {2,1}, {2,0} },
    { {0,0}, {0,1}, {0,2}, {1,2} },
    { {0,0}, {0,1}, {1,0}, {2,0} },
    { {0,0}, {1,0}, {1,1}, {1,2} },
    // figure 4
    { {0,0}, {1,0}, {1,1}, {2,1} },
    { {1,0}, {1,1}, {0,1}, {0,2} },
    { {0,1}, {1,1}, {1,0}, {2,0} },
    { {0,0}, {0,1}, {1,1}, {1,2} },
    //figure 5
    { {0,0}, {0,1}, {1,1}, {0,2} },
    { {1,0}, {1,1}, {0,1}, {1,2} },
    { {0,0}, {1,0}, {1,1}, {2,0} },
    { {0,1}, {1,0}, {1,1}, {2,1} }
};
 
int N, M;
int board[502][502];
 
int getMax(int x, int y){
    int result = 0;
    
    for(int i=0; i<19; i++){
        int temp = 0;
        
        for(int j=0; j<4; j++){
            int movedX = x + tetromino[i][j][0];
            int movedY = y + tetromino[i][j][1];
            if( movedX >= N || movedY >= M ){
                temp = 0;
                break;
            }
            temp += board[movedX][movedY];
        }
        
        if(result < temp)
            result = temp;
    }
    
    return result;
}
 
int main() {
    int result = 0;
    
    cin>>N>>M;
    
    for(int i=0; i<N; i++)
        for(int j=0; j<M; j++)
            cin>>board[i][j];
    
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            int temp = 0;
            temp = getMax(i, j);
            
            if(result < temp)
                result = temp;
        }
    }
    
    cout<<result<<endl;
    
    return 0;
}