백준 3164 자바 - 패턴 (BOJ 3164 JAVA)

문제 : boj3164

 

  우선 뭐 배열에 직접 그린 후에 직접 세는 방식은 O(X*Y) = O(10^12) 이므로 불가하다. 애초에 메모리도 엄청 많이 들 것이다. X와 Y가 최대 10^6 이므로 시간내에 풀기 위해서는 O(N)이나 O(NlogN) 급의 풀이가 필요하다.

 

  혹시 어떻게 푸는지 감이 안왔다면 아래의 그림을 보면 바로 아! 라고 외칠 것이다. 그래프를 2개로 나눠서 보면 쉽게 풀이법을 생각해낼 수 있다.

  문제에서 제시된 그래프 그대로 풀이를 찾기엔 좀 난해할 수 있지만, 아래와 같이 가로 성분과 세로 성분을 나눠서 생각해보면(세로 성분의 맨 위는 가로성분에 이미 포함된다.) 그냥 범위내에 포함되는 매번 +2씩 증가하는 기둥의 길이를 구하는 문제가 된다.

 

  가로 기둥 최대 50만개, 세로 기둥 최대 50만개 이므로 가로 모든 기둥을 전부 보고, 세로 모든 기둥을 전부 봐도 O(X+Y)이므로 시간내에 통과할 수 있다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(new BufferedReader(new InputStreamReader(System.in)).readLine());
        int x1 = Integer.parseInt(st.nextToken());
        int y1 = Integer.parseInt(st.nextToken());
        int x2 = Integer.parseInt(st.nextToken());
        int y2 = Integer.parseInt(st.nextToken());

        long sum = 0;
        for (int i = y1%2==1?y1+1:y1+2; i <= y2; i+=2) {
            if (i <= x1) continue;
            sum += Math.min(i, x2) - x1;
        }
        for (int i = x1%2==1?x1+1:x1+2; i <= x2; i+=2) {
            if (i-1 <= y1) continue;
            sum += Math.min(i-1, y2) - y1;
        }
        System.out.println(sum);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}