백준 10163번 [색종이](C++) -yes6686- 티스토리

 

 

백준 문제 풀이: 10163 [색종이]

---

문제 링크: https://www.acmicpc.net/problem/10163

문제 설명:

가로세로 1001×1001 크기의 도화지에 N장의 색종이를 순서대로 붙였을 때, 마지막에 보이는 각 색종이의 면적(보이는 칸 수)을 구하는 문제입니다.

각 색종이는 좌측 하단 좌표와 너비, 높이로 주어지며, 나중에 붙인 색종이가 앞의 색종이를 덮을 수 있습니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[1001][1001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    // 각 색종이 정보를 받아서 해당 위치에 색종이 번호를 기록
    for (int i = 1; i <= n; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        for (int j = a; j < a + c; j++) {
            for (int h = b; h < b + d; h++) {
                arr[j][h] = i;
            }
        }
    }

    // 각 색종이 번호가 도화지 위에 몇 칸 있는지 세기
    for (int i = 1; i <= n; i++) {
        int cnt = 0;
        for (int j = 0; j <= 1000; j++) {
            for (int h = 0; h <= 1000; h++) {
                if (arr[j][h] == i) {
                    cnt++;
                }
            }
        }
        cout << cnt << '\n';
    }
}
  

---

코드 설명

• 핵심 알고리즘: 2차원 시뮬레이션 – 도화지를 1001×1001 격자로 보고, 색종이 번호로 덮어쓰기
• 구현 세부사항:
  • arr[1001][1001]: 도화지의 각 위치에 마지막으로 덮인 색종이 번호 저장
  • 입력받은 좌표와 크기만큼 도화지에 색종이 번호로 덮기
  • 1번부터 n번까지의 색종이에 대해 도화지를 순회하며 자신의 번호가 있는 칸의 수를 카운트
• 시간 복잡도 분석:
  • 색종이 배치: O(n ⋅ w ⋅ h), 최악의 경우 O(n ⋅ 1000 ⋅ 1000)
  • 출력 계산: O(n ⋅ 1001²)
  • 1001×1001 도화지 순회는 허용 가능한 수준

---

결과

예시 입력:

3
3 2 5 3
15 7 4 4
5 2 3 3
  

예시 출력:

6
16
9

세 번째 색종이가 일부 첫 번째 색종이를 덮었기 때문에 1번과 3번 색종이 면적이 감소합니다.

다른 접근 방식이나 최적화 아이디어가 있다면 댓글로 함께 나눠주세요!