[코드트리] 기울어진 직사각형

       문제 요약        

- 문제

 

N x N 격자 안에 말그대로 기울어진 직사각형을 그리고 

그 선이 지나는 칸에 적힌 수들의 합의 최대를 구하는 문제

 

         아이디어        

두 변의 길이가 변화해서 처음에는 어떻게 해야 할지 고민이 있었다 

 

         소스코드        

 

import java.io.*;
import java.util.*;
public class Main {
    static int N;
    static int[][] box;
    static int[][] way = {{-1, 1}, {-1, -1},{1, -1}, {1, 1}};
    static int maxSum = 0;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        box = new int[N][N];
        for(int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++){
                box[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int minLen = 1;
        int maxLen = N - 1;

        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                for(int a = minLen; a <= maxLen; a++) { // 변의 길이(1)
                    for(int b = minLen; b <= maxLen; b++) { // 변의 길이(2)
                        travel(i, j, a, b);
                    }                    
                }
            }
        }

        System.out.println(maxSum);
    }

    static void travel(int i, int j, int a, int b) {
        int x = i, y = j;

        boolean isAnswer = true;
        int sum = 0; // 처음에 0으로 둔 이유는 어차피 첫 지점으로 돌아올 거기 때문이다
        for(int w = 0; w < 4; w++) {
            int moveCnt = b;
            if(w % 2 == 0) { // a b a b << 변의 길이 
                moveCnt = a;
            }
            while(moveCnt-- > 0) {
                int nx = x + way[w][0];
                int ny = y + way[w][1];
                if(nx < 0 || nx >= N || ny < 0 || ny >= N) {
                    isAnswer = false;
                    break;
                }
                x = nx;
                y = ny;   
                sum += box[x][y]; 
            }
            if(!isAnswer){
                return;
            }
        }
        if(isAnswer) {
            maxSum = Math.max(maxSum, sum);
        }
    }
}

 

길이에 대한 범위가 있고 (이것도 선택해야 함)

그 길이를 선택했을 때 범위를 넘어가는지도 확인해야 함