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

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

문제에서 요구하는 시간복잡도 계산은 어떤식으로 하면 되나요?

일반적으로 코드가 1억 번 동작 한다면 1초의 런타임이 소요 된다고 생각하시면 좋을 것 같습니다.

이 문제에서 n 은 최대 20 이며, 20^5=3_200_000이기 때문에 코드가 넉넉하게 돌아가게 됩니다.

실제 테스트에서도 작성하신 코드가 최대 1억번 이상 동작하는지 안하는지를 생각해보자!

🗒️알고리즘 분류

#완전 탐색 #brute force

📌기억해야 할 포인트

처음에 직사각형의 크기를 방향과 count 를 통해서 가로, 세로의 길이를 모두 반복문과 제어문으로 제어하려고 했다. 하지만, 그렇게 하려고 하니 코드가 너무 복잡해졌고 결국 코드가 산으로 갔다…

• 결국 완전 탐색을 해야 하는 문제이므로 임의의 점을 기준으로 반복문을 통해 width, height 를 정해주고, 그 다음에 직사각형 각 원소들의 합을 구하면 된다.
  • int[] length = {width, height, width, height};
  • 만약 직사각형의 좌표 중 하나라도 범위를 벗어난다면 (!isInRange()) 바로 0 을 return 해주면 된다.

📝풀이 코드(JAVA)

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

public class Main {
    private static int N = 0;
    private static int[] DX = {1,-1,-1,1};
    private static int[] DY = {1,1,-1,-1};

    public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(); 
        int[][] arr = new int[n][n]; 

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
        sc.close();

        N = n;
        int answer = 0;

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int w = 1; w < n; ++w) {
                    for (int h = 1; h < n; ++h) {
                        answer = Math.max(answer, getSum(arr, i,j,w,h));
                    }
                }
            }
        }
        
        System.out.println(answer);
        return;
    }

    private static int getSum(int[][] arr, int x, int y, int width, int height) {
        int result = 0;
        int[] length = {width, height, width, height};

        for (int d = 0; d < 4; ++d) {
            for (int step = 0; step < length[d]; ++step) {
                x += DX[d];
                y += DY[d];

                if (!isInRange(x, y)) {
                    return 0;
                }
                result += arr[x][y];
            } 
        }

        return result;
    }

    private static boolean isInRange(int x, int y) {
        return 0 <= x && x < N && 0 <= y && y < N;
    }
}

⏰총 풀이시간

• 70분