알고리즘 문제 해결(PS)/[백준]

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

연구소장 J 2022. 2. 18. 11:28

문제

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

 

1531번: 투명

첫째 줄에 N과 M이 주어진다. N은 0보다 크거나 같고, 50보다 작거나 같다. M은 0보다 크거나 같고, 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 종이의 좌표가 주어진다. 왼쪽 아래 모서리의 x, y좌

www.acmicpc.net

풀이

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

 

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

백준 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 해주면 된다.

 

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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);        
    }
}
 
cs

결과

1531 결과

반응형