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

문제링크

문제 설명

n이 주어지고 n * n개의 숫자가 주어진다.
이 숫자들안에서 기울어진 직사각형으로 돌며 값을 더할 때, 최대가 되는 값을 구하라.
도는 방향은 ↗️↖️↙️↘️이다.
↙️↖️
↘️↗️
즉, 위 모양처럼 직사각형의 모양을 띌 수 있다.

문제 접근

• 모든 직사각형의 경우를 다 판단한다.
• 최대가 되는 값을 구하기 위해, 최대 크기의 직사각형을 구한다.

잘못된 생각

• ↖️ ↗️ 두가지 방향의 직사각형만 생각하여 구현
  각각 짝수번째와 홀수번째의 길이가 1씩만 되도록 구현하여
  원하는 최대 값이 나오지 않았다.

문제 풀이 코드 (사각형의 넓이를 구하는 부분)

    public static int find_sum(int i, int j){
        int ret = 0;

        for (int odd = 1; odd <= n; odd++){
            for (int even = 1; even <= n; even++){
                int sum = 0;
                boolean valid = true;

                int x = i;
                int y = j;

                // 1
                for (int k = 0; k < odd; k++){
                    x--;
                    y++;
                    if (x < 0 || y >= n){
                        valid = false;
                        break;
                    }
                    sum += lst[x][y];
                }

                if (!valid)
                    continue;

                // 2
                for (int k = 0; k < even; k++){
                    x--;
                    y--;
                    if (x < 0 || y < 0){
                        valid = false;
                        break;
                    }
                    sum += lst[x][y];
                }
                if (!valid)
                    continue;

                // 3
                for (int k = 0; k < odd; k++){
                    x++;
                    y--;
                    if (x >= n || y < 0){
                        valid = false;
                        break;
                    }
                    sum += lst[x][y];
                }
                if (!valid)
                    continue;

                // 4
                for (int k = 0; k < even; k++){
                    x++;
                    y++;
                    if (x >= n || y >= n){
                        valid = false;
                        break;
                    }
                    sum += lst[x][y];
                }
                if (!valid)
                    continue;     

                ret = Math.max(sum, ret);           
            }
        }

        return ret;
    }

• for문으로 짝수번째 길이와 홀수번째 길이를 늘려가면 그때 그때의 최대 값을 갱신하였다.
• 주어진 숫자들 안에서 최대한으로 갈 수 있는 만큼 더하도록 구현하였다.
  (주어진 길이만큼)