[코딩테스트 37일차] BAEKJOON 2563번 : 색종이

[BAEKJOON 2563번 : 색종이]

[문제]

---

[고찰]

해당 문제에 대해 아이디어가 너무 떠오르지 않아, 잘못된 풀이일거라는 직감이 있었지만 어떻게든 풀기 위해 아래와 같이 풀게 되었습니다.

결과는 물론 틀렸기는 합니다만.. 모든 경우의 수를 고려했다고 생각했는데 아니였던 것 같습니다.

 

이에 올바른 풀이를 정리하고자 합니다.

 

#include <iostream>
#include <vector>     

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;

	vector<pair<int, int>> squares(n);

	int blackArea = 0;
	int area = 100 * n;

	for (int i = 0; i < n; i ++)
	{
		cin >> squares[i].first >> squares[i].second;
	}

	for (int i = 0; i < squares.size() - 1; i++)
	{
		for (int j = i + 1; j < squares.size(); j++)
		{
			int a = squares[i].first; int b = squares[i].second;
			int x = squares[j].first; int y = squares[j].second;

			if (a < x && x < a + 10)
			{
				if (b < y + 10 && y + 10 < b + 10)
				{
					blackArea += (a + 10 - x) * (y + 10 - b);
				}
				else if (b < y && y < b + 10)
				{
					blackArea += (x - a + 10) * (b + 10 - y);
				}
				else if (y == b)
				{
					blackArea += (a + 10 - x) * 10;
				}
			}
			else if (a < x + 10 && x + 10 < a + 10)
			{
				if (b < y + 10 && y + 10 < b + 10)
				{
					blackArea += (x + 10 - a) * (y + 10 - b);
				}
				else if (b < y && y < b + 10)
				{
					blackArea += (x + 10 - a) * (b + 10 - y);
				}
				else if (y == b)
				{
					blackArea += (x + 10 - a) * 10;
				}
			}
			else if (a == x)
			{
				if (b < y + 10 && y + 10 < b + 10)
				{
					blackArea += 10 * (y + 10 - b);
				}
				else if (b < y && y < b + 10)
				{
					blackArea += 10 * (b + 10 - y);
				}
				else if (y == b)
				{
					blackArea += 10 * 10;
				}
			}
		}
	}

	cout << area - blackArea;

	return 0;
}

---

[개념]

해당 문제를 풀기 위한 아이디어는 도화지를 고려하여, 색칠한 부분만 계산하는 것입니다.

물론 저도 이 방법을 못떠올린 것은 아니지만, 이를 구현할 능력이 부족하였었습니다..

 

일단 도화지를 100 x 100으로 초기화하는데, bool 타입의 2차원 배열을 만듭니다.

 

n번만큼 색종이를 입력 받을 때, 그 색종이에 해당하는 부분을 색칠합니다.

이중 for문으로, i가 x부터 x + 10까지, j가 y부터 y + 10까지 반복하면서

paper[ i ][ j ]를 true로 바꾸어 색칠한 것으로 칩니다.

이후 area를 1 더해주면 됩니다.

 

겹쳐진 부분은 칠하면 안되기 때문에, 이중 for문에 if문을 추가하여, 이를 방지합니다.

if (!paper[ i ][ j ])로 이를 확인해주면, 색칠한 부분은 다시 색칠하지 않습니다.

 

이를 코드로 구현하면 아래와 같습니다.

while (n--)
{
	int x, y;
	cin >> x >> y;

	for (int i = x; i < x + 10; i++)
	{
		for (int j = y; j < y + 10; j++)
		{
			if (!paper[i][j])
			{
				paper[i][j] = true;
				area++;
			}
		}
	}
}

---

[정리]

이런 문제를 푸는 것은, 코딩테스트 쪽으로 머리가 잘 굴러가야하는 것 같습니다.

더욱 증진해보겠습니다.

---

[Solution]

#include <iostream>
using namespace std;

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

    int n;
    cin >> n;

    bool paper[100][100] = { false };
    int area = 0;

    while (n--)
    {
        int x, y;
        cin >> x >> y;

        for (int i = x; i < x + 10; i++)
        {
            for (int j = y; j < y + 10; j++)
            {
                if (!paper[i][j])
                {
                    paper[i][j] = true;
                    area++;
                }
            }
        }
    }

    cout << area;
    
    return 0;
}