[자바] 백준 18221 - 교수님 저는 취업할래요 (boj java)

문제 : boj18221

 

  문제 제목이 상당히 무섭고, 지문이 길긴 하지만 정리해보면 결국 알아야 하는건 어렵지 않다. 알아내야 하는걸 정리해보자.

1. 성규가 앉은 위치의 좌표

2. 교수님이 앉은 위치의 좌표

3. '1'과 '2'의 거리가 5이상인지

4. '1'과 '2'로 만들어지는 직사각형 혹은 선 위에 몇 명의 학생이 있는지

 

  위와 같이 알 수 있으면 풀 수 있다. '1'과 '2'는 입력을 받으면서 알 수 있다.

 

  '3'은 문제에서 제시된 공식으로 알 수 있다. 다만, double로 처리하는건 항상 소수점 오차의 문제가 생길 가능성이 있다. 따라서 아래와 같이 공식을 바꿔서 int내에서 처리가 되도록 하자. 이하의 조건을 만족하지 않는다면 바로 0을 출력하고 종료하면 된다.

 

  '4'의 경우엔 결국 직사각형의 좌측상단과 우측상단만 알면 그 내부를 2중 반복문을 통해 직접 확인하면 된다. 그렇게 하더라도 최악의 경우에도 O(N^2)개만 확인하면 되므로 시간은 널널하다.

 

  교수의 위치가 (a,b), 성규의 위치가 (c,d)라고 하면 반복문의 수도코드는 다음과 같다. arr은 입력받은 배열이다.

for i가 (min(a, c)부터 max(a, c)까지):
   for j가 (min(b, d)부터 max(m, d)까지):
       arr[i][j]가 1이라면 학생이므로 카운팅

카운팅한 결과가 3 이상이면 1, 미만이면 0을 출력해주면 된다.

 

  이하 코드의 경우에는 시간복잡도를 O(N)으로 변경하기 위해 입력을 받으면서 prefix sum 배열을 만든 경우이다. 이 경우 1차원 배열의 범위 합을 O(1)로 구할 수 있다. 이 문제를 통과하데는 굳이 필요없다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n+1][n+1];
        int[] a = new int[2];
        int[] b = new int[2];
        for (int i = 1; i <= n; i++) {
            String s = br.readLine();
            for(int j = 1; j <= n; j++) {
                switch(s.charAt((j-1)*2)) {
                    case '1': arr[i][j] = 1; break;
                    case '2': a[0]=i; a[1]=j; break;
                    case '5': b[0]=i; b[1]=j; break;
                }
                arr[i][j] += arr[i][j-1];
            }
        }
        if ((a[0]-b[0])*(a[0]-b[0])+(a[1]-b[1])*(a[1]-b[1])<25){
            System.out.println(0);
            return;
        }
        int rs = a[0]<b[0]?a[0]:b[0];
        int re = a[0]<b[0]?b[0]:a[0];
        int cs = a[1]<b[1]?a[1]:b[1];
        int ce = a[1]<b[1]?b[1]:a[1];
        int cnt = 0;
        for (int i = rs; i <= re; i++) cnt += arr[i][ce]-arr[i][cs-1];
        System.out.println(cnt>=3?1:0);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}