[백준] 1531번 투명 (자바풀이)

문제

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

1531번: 투명

풀이

처음에 문제가 잘 이해가 안됐는데 다음과 같이 그림으로 이해하면 간단하다.

 

예제를 예시로 들면 다음과 같다.

예제는 M이 1이였으므로, 2개 이상의 종이가 겹쳐야 그림이 보이지 않는다.

따라서 (41,41)~(60,60) 부분의 그림 400개(20*20)와, (71,71)~(80,80) 부분의 그림 100개(10*10)를 합쳐서 500개의 그림이 보이지 않는 것이다.

 

해결법은 매우 간단하다. 그저 int[101][101] 배열에 입력이 들어온 좌표대로 수를 1를 증가시키면 된다.

이후 모든 배열의 원소를 돌면서 M보다 원소값이 크다면 count 해주면 된다.

 

코드

import java.util.*;
import java.io.*;
 
public class Baekjoon_1531 {
    static int N,M;
    static int picture[][] = new int[101][101];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        
        for(int i=0; i<N; i++) {
            int x1 = sc.nextInt();
            int y1 = sc.nextInt();
            int x2 = sc.nextInt();
            int y2 = sc.nextInt();
            for(int j=x1; j<=x2; j++) {
                for(int k=y1; k<=y2 ; k++) {
                    picture[j][k] += 1;
                }
            }
        }
        
        int ans = 0;
        for(int i=1; i<=100; i++) {
            for(int j=1; j<=100; j++) {
                if(picture[i][j] > M) ans++;
            }
        }
        System.out.println(ans);        
    }
}
 

결과