[백준] 2536 번 : 색종이 (C++)

01. 문제

 

02. 소스코드

 

- 방법 1 : 2차원 배열

#include<iostream>
using namespace std;

int square[100][100] = {0, }, n, w, h, result = 0;
int main()
{
    cin >> n;
    
    while (n--)
    {
        cin >> w >> h;
        for (int i = w; i < w + 10; i++)
        {
            for (int j = h; j < h + 10; j++)
                if (square[i][j] == 0)
                {
                    result++;
                    square[i][j] = 1;
                }
        }
    }
    
    cout << result;
    return 0;
}

 

03. 풀이

 

- 풀이 1 : 2차원 배열

 

흰색 정사각형의 변 길이가 100이니, 가로 100 세로 100 형태의 2차원 배열을 만들고

검은 정사각형이 붙여진 넓이를 알기 위해서 흰색 정사각형 배열을 0으로 초기화 해준다.

int square[100][100] = {0, }

검은 정사각형의 가로 세로 시작 위치를 입력 받고 나서

이미 같은 위치에 붙여진 사각형이 있는지 체크한다.

정사각형의 해당 위치의 값이 0일 경우 아무것도 붙은 적이 없다는 뜻이니

result 의 값을 + 1 해준 다음, 중복 계산 방지를 위해 해당 위치 값을 1로 바꿔준다.

for (int i = w; i < w + 10; i++)
{
	for (int j = h; j < h + 10; j++)
		if (square[i][j] == 0)
		{
			result++;
			square[i][j] = 1;
		}
}

 

추가 설명을 위해 예를 들어보면,

한 변의 길이가 5인 정사각형을 square[5][5] = {0, } 으로 초기화해주면

{0} {0} {0} {0} {0}

{0} {0} {0} {0} {0}

{0} {0} {0} {0} {0}

{0} {0} {0} {0} {0}

{0} {0} {0} {0} {0}

이런 형태로 배열 바구니가 0으로 채워져 있다.

 

왼쪽변과 2, 아래쪽 변과 2 떨어진 곳에 한 변의 길이가 3인 정사각형을 붙인다면

{0} {0} {1} {1} {1}

{0} {0} {1} {1} {1}

{0} {0} {1} {1} {1}

{0} {0} {0} {0} {0}

{0} {0} {0} {0} {0}

0은 아무것도 붙어있지 않는 상태를 표현했기에 사각형을 붙인 부분을 1로 바꿔준 뒤

1이 채워진 바구니의 개수만 체크하면 수월하게 풀이가 가능하다.

 

주의할 점은,

1이 채워진 바구니 (사각형이 붙은 바구니) 에 또 다른 사각형을 붙일 때는

중복체크 하면 안되기 때문에 사각형을 추가로 붙일 때마다 0일 경우만

카운트를 증가시켜주면 된다.

 

 

 

 

 

 

2563번: 색종이 (acmicpc.net)

2563번: 색종이