[BOJ] 2563 색종이 - JAVA

1. 문제

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

2563번: 색종이

• 100*100 도화지에 10*10 색종이를 붙인다.
• 색종이가 붙은 면적을 계산한다. (겹친 면적은 한 번만 계산돼야 함)

---

2. 풀이

처음에는 색종이의 개수*100 - 겹친 면적 <-방식으로 푸려고 했다. 하지만 이 방법은 색종이를 가로 위치대로 정렬한 뒤 바로 다음 색종이와의 비교만 하게 되기 때문에 두 장 이상이 겹친다면 구할 수 없다.

그래서 그 다음으로 선택한 방법은 도화지 100*100 배열을 준비한 뒤, 색종이가 추가될 때마다 색종이가 놓일 자리에 표시를 해주는 것이다.

이미 방문했던 자리인지 체크할 필요 없이 계속 저장해도 되지만, 나중에 출력을 위한 반복문을 다시 돌리지 않기 위해 if문을 이용해 카운트를 체크해줘야했다. 

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

public class BOJ_2563_색종이 {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(in.readLine());
        StringTokenizer st;

        boolean[][] papers = new boolean[101][101];
        int cnt = 0;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(in.readLine());

            int left = Integer.parseInt(st.nextToken());
            int bottom = Integer.parseInt(st.nextToken());

            for(int x = left;x<left+10;x++){
                for(int y=bottom;y<bottom+10;y++){
                    if(!papers[y][x]){
                        papers[y][x] = true;
                        cnt++;
                    }
                }
            }
        }

        System.out.println(cnt);

    }
}

---

3. 결과

한 번 틀린건 위에 있던 정렬->두개씩만 비교했던 방법이다.