[Baekjoon] 2563번: 색종이

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

2563번: 색종이

 

---

 

문제 해결 과정

착안

문제에서 주어진 핵심 조건:

• 도화지(2차원 좌표 평면)에 색종이를 붙이는 위치가 항상 자연수로 주어진다.
• 항상 정사각형 모양의 색종이를 도화지의 변과 평행하게 붙인다.
• 입력으로 주어지는 위치는 정사각형의 좌하단 좌표이다.

문제에서 직접적으로 언급된 것은 아니지만 쉽게 유추할 수 있는 것으로, 100 x 100 크기의 도화지를 두 좌표축과 평행하며 1의 간격으로 등분(10,000 등분)해서 얻은 1 x 1 크기의 정사각형은 각각 해당 사각형의 좌하단 좌표와 일대일 대응으로 대응시킬 수 있다. 즉, 좌하단 좌표가 \((m, n)\)인 1 x 1 크기의 정사각형에 색종이가 하나 이상 덮여있는지의 여부를 paper[m][n]으로 간단하게 표현할 수 있다는 것이다.

 

따라서, 색종이로 덮인 여부를 나타낼 수 있는 100 x 100 크기의 도화지(2차원 배열)를 만들고, 색종이를 붙이는 과정마다 1 x 1 크기의 정사각형에 대해 색종이의 부착 여부를 저장하여 문제를 해결할 수 있다.

 

구현

이 문제는 별다른 생각할 필요 없이, 진짜 모눈종이에 그냥 색종이를 붙이는 행위를 구현하고 색종이가 붙어있는 칸을 하나씩 세면 간단하게 풀린다.

 

그런데, 이 문제를 처음 봤을 때는 이상하게도 두 사각형의 충돌 판정법(특히, AABB)에 사로잡혀서 너무 필요 이상으로 복잡하게 계산을 하다보니 시간 초과(색종이를 붙일 때마다 계속 기존에 붙어있는 색종이들과 충돌을 판정...)로 실패했었다. 문제를 해결하고나서 다시 생각해봤을 때는 정말 그렇게 바보같은 생각이 아닐 수 없었다...

 

코딩 문제를 접해본 경험이 많지 않아서 한 번 생각이 사로잡히면 좀처럼 새로운 방법이 떠오르지가 않는데, 이 문제를 계기로 어릴 적 한창 수학을 공부할 때처럼 문제가 풀리지 않으면 다른 방법으로 새롭게 접근하는 것이 중요하다는 것을 다시 한 번 생각해보게 되었다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	bool coords[100][100]{ 0, };
	unsigned short area = 0;
	unsigned short n;
	cin >> n;

	for (unsigned short i = 0; i < n; i++)
	{
		unsigned short min[2] = { 0, 0 };
		cin >> min[0];
		cin >> min[1];

		for (int y = min[1]; y < min[1] + 10; y++)
		{
			for (int x = min[0]; x < min[0] + 10; x++)
			{
				if (!coords[x][y])
				{
					coords[x][y] = true;
					area++;
				}
			}
		}
	}

	cout << area;

	return 0;
}

 

실행 결과

* 코드를 제출한 시점과 글 작성 시점이 달라, 주석 추가 등의 이유로 실행 결과의 코드 길이는 상이할 수 있음.