[Java] Boj 1531: 투명

2025. 2. 22. 12:11·PS/Solve

문제

세준이는 1×1크기의 그림으로 모자이크한 100×100크기의 그림을 가지고 있다. 어느 날 이 모자이크 중 일부 그림이 너무 보기 싫어서 N개의 불투명한 종이로 그림을 가리기 시작했다. 불투명한 종이로 가린다고 항상 그 그림이 안 보이는 것은 아니다. 그 그림의 현재 부분 위에 M개 이하의 종이가 올려져 있으면 그림은 그 부분에서 보이게 된다.

그림의 크기는 100×100이고, N개의 종이는 왼쪽 아래 모서리 좌표와 오른쪽 위 모서리 좌표가 입력으로 들어온다. 또, 종이가 가리는 영역에는 두 모서리의 좌표도 포함된다. 예를 들어, (1,1)부터 (2,2)를 가린다면, 총 4개의 그림이 가려진다. (1,1), (1,2), (2,1), (2,2).

100×100크기의 모자이크 중에 보이지 않는 그림의 개수를 세는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. N은 0보다 크거나 같고, 50보다 작거나 같다. M은 0보다 크거나 같고, 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 종이의 좌표가 주어진다. 왼쪽 아래 모서리의 x, y좌표, 오른쪽 위 모서리의 x, y좌표 순으로 주어진다. 모든 좌표는 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 출력한다.


풀이

그리 어렵지 않은 구현 문제로 100 * 100 크기의 2차원 배열을 만들고, 입력받은 좌하단 모서리 좌표와 우상단 모서리 좌표를 통해 해당 구간의 값을 1씩 증가시킨다. 

( (1, 1) (3, 3)을 입력받으면 arr[1][1], arr[1][2], arr[1][3], arr[2][1], ..., arr[3][3]의 값을 1 증가시키는 형태)

입력받는 모서리들의 좌표를 기반으로 해당 구간의 배열 값을 1씩 증가시키고, 마지막으로 100 * 100 배열의 값이 M보다 큰 값이 크다면 cnt 값을 증가시켜 출력한다.

 

코드

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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int[][] arr = new int [101][101];
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        for (int i=0; i<n; i++) {
            st = new StringTokenizer(bf.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());
            for (int x = x1; x <= x2; x++) {
                for (int y = y1; y <= y2; y++) {
                    arr[x][y]++;
                }
            }
        }
        int cnt = 0;
        for (int i=1; i<101; i++) {
            for (int j=1; j<101; j++) {
                if (arr[i][j] > m) cnt++;
            }
        }
        System.out.println(cnt);
    }
}
Colored by Color Scripter
cs

'PS > Solve' 카테고리의 다른 글

[Java] Boj 1895: 필터  (0) 2025.02.22
[Java] Boj 11899: 괄호 끼워넣기  (0) 2025.02.22
[Java] Boj 11659: 구간 합 구하기 4  (0) 2025.02.21
[Java] Boj 1316: 그룹 단어 체커  (0) 2025.02.21
[Java] Boj 10867: 중복 빼고 정렬하기  (1) 2025.02.20
'PS/Solve' 카테고리의 다른 글
  • [Java] Boj 1895: 필터
  • [Java] Boj 11899: 괄호 끼워넣기
  • [Java] Boj 11659: 구간 합 구하기 4
  • [Java] Boj 1316: 그룹 단어 체커
hyeon0117
hyeon0117
컴공으로 살아남기
  • hyeon0117
    컴공 생활기
    hyeon0117
  • 전체
    오늘
    어제
    • 분류 전체보기 (57)
      • Algorithm (2)
      • PS (19)
        • Solve (19)
      • CS (36)
        • 객체지향설계 & 패턴 (12)
        • COLMAP (2)
        • 머신러닝 (1)
        • 프로그래밍 언어론 (19)
        • 형식언어 (1)
        • 운영체제 (1)
  • 블로그 메뉴

    • 홈
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    자료구조
    다이나믹 프로그래밍
    객체지향
    형식언어
    프로그래밍 언어론
    의미론
    java
    BOJ
    그리디 알고리즘
    객체지향설계
    구현
    최단 경로
    PS
    언어 타입
    boj 1343
    형식언어론
    디자인패턴
    자료형
    알고리즘
    백준 25418
    블록 구조 언어
    디자인 패턴
    백준 6825
    soild 패턴
    어휘 분석기
    함수
    PLT
    객체지향언어
    선택 정렬
    백준
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
hyeon0117
[Java] Boj 1531: 투명
상단으로

티스토리툴바