색종이 넓이 계산 백준 2563, C++

🧩 색종이 성공 - 겹치는 영역까지 정확히 구하는 넓이 계산

---

문제 사이트

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

📌 문제 설명

100×100 크기의 흰색 도화지가 있습니다.
이 도화지 위에 10×10 크기의 검은색 색종이를 여러 장 붙입니다.
색종이는 도화지 바깥으로 벗어나지 않으며, 붙일 때 색종이의 왼쪽 아래 모서리 좌표가 주어집니다.

색종이들이 겹칠 수 있기 때문에, 겹친 부분은 한 번만 계산해야 합니다.
목표는 도화지 위에 붙은 검은 영역의 총 넓이(=면적)를 구하는 것입니다.

---

✅ 예시 입력 및 출력

입력

3
3 7
15 7
5 2

출력

260

위의 예에서는 색종이 3장을 붙였고, 겹친 부분을 정확히 고려했을 때 총 넓이는 260입니다.

---

💡 문제 해결 아이디어 (접근 방법)

1. 현실에서 문제를 푼다면?

• 직접 100×100 격자 위에 색종이를 붙여가며 색칠을 하겠죠.
• 같은 곳에 색칠이 되더라도 이미 칠해진 곳은 다시 칠하지 않음.
• 마지막에 칠해진 전체 면적을 셀 수 있습니다.

2. 고민했던 다른 아이디어들

• 색종이 좌표들을 받아서 넓이를 직접 계산할까?
• 겹친 부분을 어떻게 빼야 하나?
• 이건 겹침 판정이 복잡하므로 오히려 비효율적.

3. 결론

“직접 도화지에 색칠해 보자!”
2차원 배열로 도화지를 만들고 색종이를 붙이는 부분을 1로 채운 뒤,
마지막에 1의 개수를 세면 된다!

---

💻 내 코드 분석

전체 코드

#include <iostream>
#include <cstring>
using namespace std;

int arr[100][100] = { 0, };  // 도화지를 나타내는 100x100 배열

int main(void)
{
    int n, col, row, sumOfarr = 0;
    cin >> n;

    // 색종이 하나씩 붙이기
    for (int k = 0; k < n; k++)
    {
        cin >> col >> row;
        for (int i = row; i < row + 10; i++)  // 세로 방향 10칸
        {
            for (int j = col; j < col + 10; j++)  // 가로 방향 10칸
            {
                arr[i][j] = 1;  // 색칠 (덮어쓰기여도 상관 없음)
            }
        }
    }

    // 전체 도화지에서 색칠된 부분 카운트
    for (int i = 0; i < 100; i++)
    {
        for (int j = 0; j < 100; j++)
        {
            if (arr[i][j] == 1)
                sumOfarr++;
        }
    }

    cout << sumOfarr << endl;
    return 0;
}

---

🔍 코드 상세 리뷰

1. 2차원 배열 초기화

int arr[100][100] = { 0, };

도화지를 100×100의 배열로 선언합니다.
모든 칸을 0으로 초기화 (아무 색종이도 안 붙은 상태).

2. 색종이 좌표 입력 후 색칠

cin >> col >> row;
for (int i = row; i < row + 10; i++) {
    for (int j = col; j < col + 10; j++) {
        arr[i][j] = 1;
    }
}

색종이 한 장의 아래 왼쪽 꼭짓점 좌표 입력.
그 위치부터 오른쪽으로 10칸, 위로 10칸을 1로 칠함.
겹쳐도 덮어쓰기만 하므로 문제가 없습니다.

3. 색칠된 영역 넓이 계산

for (int i = 0; i < 100; i++) {
    for (int j = 0; j < 100; j++) {
        if (arr[i][j] == 1)
            sumOfarr++;
    }
}

도화지를 전체 탐색하면서 색칠된 칸(1)을 셉니다.
최종적으로 넓이는 sumOfarr에 저장됩니다.

---

🔧 개선점 / 보완점

✅ 1. 배열 인덱스 방향 이해

• 이 문제에서는 (0, 0)이 도화지의 왼쪽 아래라고 할 수 있습니다.
• C++에서는 배열의 행이 위에서 아래로, 열이 왼쪽에서 오른쪽으로 증가하므로
  • arr[row][col] 순서가 헷갈릴 수 있습니다.
• 하지만 이 문제는 상하 대칭이기 때문에 배열 방향에 신경 안 써도 됩니다.

✅ 2. 배열 범위 주의

• 색종이 크기는 항상 10이기 때문에
  • (col + 10) 또는 (row + 10)이 100을 초과하지 않는다고 문제에서 보장합니다.
• 그래도 실제 개발에서는 이런 경계 조건 검사가 필수입니다.

✅ 3. 시간 복잡도

• 입력 색종이 수는 최대 100
• 색칠 과정은 색종이당 최대 100칸 → 최대 10,000번 연산
• 최종 계산도 100×100
• 전체 시간 복잡도는 O(10,000) → 매우 빠름 (문제에서 시간 제한 1초 안에 충분)

---

📚 결론

이 문제는 단순하지만 겹침을 어떻게 처리할지 고민하게 만듭니다.
최적화된 알고리즘보다 "실제 행동을 흉내 내는" 시뮬레이션 방식이 더 직관적이고 효율적일 수 있다는 점을 보여줍니다.

🎯 핵심 교훈: 복잡하게 계산하려고 하지 말고, 먼저 직접 해보는 방법을 떠올려보자.

---