[Java]백준_2563 : 색종이

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

 

 

 

 

 

문제 분석

여러 x좌표와 y좌표로 겹치는 부분 제외 넓이 계산 -> 2차원 배열로 풀어보기

도화지의 넓이는 100x100 이고, 색종이의 넓이는 10x10이고, 색종이의 수는 100 이하로 정해져 있다.

도화지 상의 좌표를 그대로 인덱스로 활용하기 위해 101 크기의 2차원 배열로 지정해놓고, 색종이를 붙일 때마다 해당 영역(10x10)을 순회하면서 새로 덮는 지점만 카운트해주면 된다.

 

 

 

소스 코드 (⭕)

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int[][] arr = new int[101][101];

        int n = Integer.parseInt(br.readLine());

        int total = 0;
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());


            for (int j = a; j < a + 10; j++) {
                for (int k = b; k < b + 10; k++) {
                    if (arr[j][k] == 0) {
                        arr[j][k] = 1;
                        total++;
                    }
                }
            }
        }
        System.out.println(total);
    }
}

 

코드 분석

1. 100x100 크기의 도화지를 표현하기 위해 101x101 크기의 2차원 배열을 선언한다.

 

2. 색종이의 개수를 입력받고, 검은 영역의 총 넓이를 저장할 변수 total을 선언한다.

 

3. n개의 색종이에 대한 a, b 좌표를 입력받고, 이중 반복문을 사용하여 (a, b)부터 (a+9, b+9)까지 색종이가 차지하는 모든 위치를 확인한다.

 

4. 만약, 해당 위치가 흰색이라면(==0), 검정으로 표시(=1)하고, 총 넓이를 1 증가시킨다. 해당 위치가 이미 색종이로 덮인 검정이라면(==1) 중복 계산하지 않는다.

 

5. 최종적으로 중복된 영역 제외한 색종이의 모든 넓이를 total로 구할 수 있다.

 

 

 

end

처음 이 문제를 봤을 때 단순히 x좌표랑 x+10좌표랑 다 구해서 겹치면 빼서 겹치는 영역 좌표 구하고 어쩌고로 생각해서 시도해보다가 도저히 막막해서 이 방법이 아닌 것 같다고 생각했다. 고민해보다가 슬쩍 검색으로 풀이를 봤는데, 넓이 하나하나를 점으로 생각해서 푸는 방법이 있었다. 바로 따라했더니 아주 쉽게 풀렸다. 사고 능력이 부족하단걸 항상 느낀다ㅠㅠ 문제적 남자 같은걸 봐야하나.. ?ㅠ0ㅜ