[백준] 1117: 색칠 1 - JAVA

https://www.acmicpc.net/problem/1117

 

풀이

W x H 크기의 종이를 가로로 f지점에서 접어 왼쪽이 오른쪽 위로 올라오게 접는다.

 

그 후 세로로 (c + 1) 등분한다.

 

(x1, y1), (x2, y2)의 지점에 색칠을 하는데, 이 때 겹쳐있는 부분 모두 색칠된다.

 

색칠이 안된 부분의 크기를 구해야 한다.

 

처음에는 W x H크기의 배열을 만들어 접는 식으로 구현했다. 이 방법으로 정답은 나왔지만 제출하니 메모리 초과가 발생했다.

 

그래서 배열을 만들지 않고 바로 뺄 수 있지 않을까 생각했다.

 

먼저 가로로 접히는 부분을 구해줘야 한다. f가 W / 2보다 크다면 왼쪽 부분이 더 길어져 색칠할 때 오류가 생긴다.

 

따라서, f가 W/2보다 클 때는 접히는 부분을 W - f로 설정해주었다.

 

그 후 세로로 접으면서 (x1, y1) (x2, y2)의 직사각형을 찾아 전체 크기인 W x H에서 빼주어야한다.

 

해당 직사각형이 가로로 접은 부분에 겹치는지 따져줘야 한다.

 

따라서, 겹치는 부분의 영역에서 색칠할 직사각형의 가로 길이는 Math.max(0, Math.min(w - x1, x2 - x1)로 해주었다.

 

직사각형이 해당 영역에 포함되지 않는다면 0이 나올것이다.

 

겹치지 않는 부분의 가로 길이는 Math.max(0, Math.min(x2 - x1, x2 - w)로 설정했다.

 

겹치는 부분은 최종적으로 곱하기 2 해주었다.

 

색칠한 부분의 크기를 계산하여 W x H에서 빼주면 끝.

 

---

 

메모리: 14192KB
시간: 128ms
언어: Java 11

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long W = Long.parseLong(st.nextToken());
        long H = Long.parseLong(st.nextToken());
        long f = Long.parseLong(st.nextToken());
        long c = Long.parseLong(st.nextToken());
        long x1 = Long.parseLong(st.nextToken());
        long y1 = Long.parseLong(st.nextToken());
        long x2 = Long.parseLong(st.nextToken());
        long y2 = Long.parseLong(st.nextToken());

        long answer = W * H;

        long w = f <= W / 2 ? f : W - f;
        answer -= (Math.max(0, Math.min(w - x1, x2 - x1)) * (y2 - y1) * (c + 1) * 2);
        answer -= (Math.max(0, Math.min(x2 - x1, x2 - w)) * (y2 - y1) * (c + 1));

        System.out.println(answer);
    }
}