[코드트리] 트로미노

🔗문제 보러 가기

 

 

두 개의 블럭 중 왼쪽블럭을 2*2의 정사각형 블록이라 생각하여, 2*2 크기의 정사각형 블록 1가지, 1*3 크기의 직사각형 블록 1가지, 3*1 크기의 직사각형 블록 1가지 이렇게 총 3가지 모양의 직사각형이 있다고 생각하였다.

그리고 정사각형 블록 값을 모두 더한 후, 각 한 조각씩 없는 4가지의 세부적인 경우로 나눠 생각했다.

 

import java.io.*;
import java.util.*;

public class Main {
    static int N, M;
    static int[][] board;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        board = new int[N][M];

        
        for(int y=0; y<N; ++y){
            st = new StringTokenizer(br.readLine());
            for(int x=0; x<M; ++x){
                board[y][x] = Integer.parseInt(st.nextToken());
            }
        }
        
        int ans = Integer.MIN_VALUE;
        for(int y=0; y<N-1; ++y){
            for(int x=0; x<M-1; ++x){
                ans = Math.max(ans, findMaxNum(y, x));
            }
        }
        for(int y=0; y<N; ++y){
            for(int x=0; x<M-2; ++x){
                ans = Math.max(ans, findMaxNum2(y, x));
            }
        }
        for(int x=0; x<M; ++x){
            for(int y=0; y<N-2; ++y){
                ans = Math.max(ans, findMaxNum3(y, x));
            }
        }

        bw.write(Integer.toString(ans));
        bw.close();
        br.close();
        
    }
    
    static int findMaxNum(int row, int col){
        int ret=0;
        int total=0;
        for(int y=row; y<row+2; ++y){
            for(int x=col; x<col+2; ++x){
                total += board[y][x];
            }
        }
        
        for(int y=row; y<row+2; ++y){
            for(int x=col; x<col+2; ++x){
                ret = Math.max(ret, total-board[y][x]);
            }
        }  
        return ret;
    }

    static int findMaxNum2(int row, int col){
        int ret=0;
        for(int x=col; x<col+3; ++x){
            ret += board[row][x];
        }
        return ret;
    }

    static int findMaxNum3(int row, int col){
        int ret=0;
        for(int y=row; y<row+3; ++y){
            ret += board[y][col];
        }
        return ret;
    }
}

 

그런데, 이런 방법외에도 3차원 배열을 이용하여 미리 모양대로 배열을 정의하여 모양의 종류만큼 반복문을 돌려, 더해주는 방법도 존재한다는 것을 알게됐다.