[2563] 색종이

난이도: ★★★☆☆ • solved on: 2025-07-05

---

문제 요약

• 문제 유형: 구현, 2차원 배열 시뮬레이션
• 요구사항:
  주어진 좌표에 10×10 크기의 색종이를 여러 장 붙였을 때, 색종이가 붙은 영역의 전체 넓이를 구해야 한다.

---

사용 개념

1. 자료구조
   • 2차원 배열 (int[][]) : 전체 평면(도화지)에서 색종이가 덮인 영역을 표시
2. 알고리즘/기법
   • 중첩 반복문으로 사각형 영역 색칠
   • 단순 카운팅
3. 핵심 키워드
   • 겹치는 부분 처리
   • 시뮬레이션(simulation)

---

풀이 아이디어 및 코드

방법 1 : 2차원 배열 전체를 사용해 직접 시뮬레이션 (직관적 / brute force)

1. 문제 분해
   • 입력 좌표마다 10×10 영역을 2차원 배열에 표시(1로 채움)
   • 모든 영역을 합산해 1이 된 칸 개수를 카운트
2. 핵심 로직 흐름

   for (각 색종이 좌표):
       for (10행):
           for (10열):
               해당 칸 extents[x + j][y + i] = 1
   결과적으로 1로 표시된 모든 칸을 합산 → 넓이

3. 예외 처리
   • 색종이가 도화지를 벗어나는 입력은 주어지지 않으므로 별도 예외 처리 필요 없음

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int nums = Integer.parseInt(br.readLine());
        int[][] papers = new int[nums][2];
        int maxWidth = 0;
        int maxHeight = 0;
        int result = 0;
        for(int i=0;i<nums;i++){
            String[] line = br.readLine().split(" ");
            papers[i][0] = Integer.valueOf(line[0]);
            papers[i][1] = Integer.valueOf(line[1]);
            if(papers[i][0]+10>maxWidth){
                maxWidth = papers[i][0]+10;
            }
            if(papers[i][1]+10>maxHeight){
                maxHeight = papers[i][1]+10;
            }
        }

        int[][] extents = new int[maxWidth][maxHeight];
        for(int[] paper:papers){
            for(int i=0;i<10;i++){
                for(int j=0;j<10;j++){
                    extents[paper[0]+j][paper[1]+i] = 1;
                }
            }
        }

        for(int i=0;i<extents.length;i++){
            for(int j=0;j<extents[i].length;j++){
                result+=extents[i][j];
            }
        }
        System.out.println(result);
    }
}

---

방법 2 : 고정 크기 도화지(100×100) 사용 & 메모리 절약

대부분 입력이 0~90 범위에만 주어지므로, 굳이 maxWidth, maxHeight를 계산하지 않고 고정 100×100 배열 사용 가능
중복된 칸을 1번만 센다는 점을 활용

1. 문제 분해
   • 100×100 도화지 배열 생성
   • 색종이 좌표에 따라 해당 10×10 영역을 1로 마킹
2. 핵심 로직

   for (입력 좌표):
       for (10행):
           for (10열):
               board[x + i][y + j] = 1
   결과적으로 1로 마킹된 칸만 카운트

3. 예외 처리
   • 입력 범위가 보장됨(0~100-10) → 오버플로우 없음

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] board = new int[100][100];
        for(int i=0;i<n;i++){
            String[] line = br.readLine().split(" ");
            int x = Integer.parseInt(line[0]);
            int y = Integer.parseInt(line[1]);
            for(int dx=0;dx<10;dx++){
                for(int dy=0;dy<10;dy++){
                    board[x+dx][y+dy] = 1;
                }
            }
        }
        int result = 0;
        for(int i=0;i<100;i++){
            for(int j=0;j<100;j++){
                if(board[i][j] == 1) result++;
            }
        }
        System.out.println(result);
    }
}

---

시간·공간 복잡도

방법 1

• 시간 복잡도: O(N × 100) (색종이 N장 × 각 10×10영역 처리)
• 공간 복잡도: O(W × H) (최대 100×100)

방법 2

• 시간 복잡도: O(N × 100) (배열 크기 고정)
• 공간 복잡도: O(1) (배열 크기 고정, 입력 크기에 무관)

---

어려웠던 점

• for문 최소화에 대한 고민 : 겹침 처리를 하려면 결국 2중 반복문을 사용해야 했다.
• 2차원 배열에 색칠하는 로직이 처음엔 직관적으로 떠오르지 않아 헤맸다.
  (행/열 or x/y 구분과 for문에 따른 증감)
• 동적으로 도화지 크기를 계산해 배열을 만들다 보니, 코드가 불필요하게 복잡해졌다.

---

배운 점 및 팁

• 문제에서 주어진 범위(0~100)를 활용하면 코드가 훨씬 간결
  (100×100 배열 고정, 복잡한 maxWidth, maxHeight 계산 불필요)
• 색종이가 겹치는 칸은 여러 번 덮여도 1번만 카운트된다.
• 시뮬레이션 문제에서 "도화지 크기"가 제한되어 있다면 무조건 고정 배열이 편하다.
• 2차원 배열 순회 시 x/y, 행/열 헷갈리지 않게 항상 변수명을 명확히 하자

---

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/2563
• 참고 블로그: 없음

---

추가 연습 문제

• 비슷한 유형 (GPT 추천):

  • [10163] 색종이 (겹친 부분의 색종이 번호 출력)
  • [2669] 직사각형 네 개의 합집합의 면적 구하기

• 확장 문제 (GPT 추천):

  • 겹친 부분의 넓이를 구하거나, 색종이별로 남은 넓이를 구하는 문제
  • 사각형끼리 겹치는 부분을 찾아내는 응용(그래픽스, CAD 등)