[BOJ] 백준 #2563. 색종이 (C++)

🎨 문제

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

• 알고리즘 분류: 구현
• 난이도: Bronze Ⅰ

💬 풀이

[100 * (색종이 수)] - (색종이들이 서로 겹치는 부분). 처음엔 이렇게 색종이들이 여러 개씩 겹치는 부분은 어떻게 처리해야 될 지 생각을 했다. 근데 벤 다이어그램 등등 이것저것 떠올리면서 아무리 생각해봐도 방법이 생각이 안나고, 다른 방향으로 접근해야 되겠구나 싶었다.

1. 가로, 세로의 길이가 각각 100인 정사각형 모양의 흰색 도화지를 bool colored[100][100]으로 생각한다.
   만약 colored[1][2]=true이면, 왼쪽 아래 꼭짓점이 (1,2)인 넓이 1인 정사각형만큼 색칠돼 있다고 생각하면 된다.
   지금까지 중복처리를 위해 마킹하는데 자주 썼던 bool배열을 그대로 이용하는 것이다.
2. 이중for문을 이용해 입력받은 좌표 기준 100칸 색칠(=true 처리)

👩‍💻 코드

C++

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

bool colored[100][100] = { false };

int main() {
	//freopen("input.txt", "rt", stdin);
	int N;
	cin >> N;

	int x, y, res = 0;
	while (N--) {
		cin >> x >> y;
		for (int i = x; i < x + 10; i++) {
			for (int j = y; j < y + 10; j++) {
				if (!colored[i][j]) {
					++res;
					colored[i][j] = true;
				}
			}
		}
	}
	
	cout << res;
	
	return 0;
}