[C++] 백준 2563 색종이

1. 문제

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

2563번: 색종이

 

2. 풀이 과정

처음에는 겹치는 부분을 제외하는 식으로 넓이를 구해야 하나 생각했는데 너무 복잡한 것 같았다.

좋은 로직을 고민을 해보다가 배열의 한칸을 넓이 1로 하는 사각형으로 생각하는 식으로 2차원 배열을 떠올렸다.

예시 사진은 11 x 11이지만 이 문제 속에서는 100 x 100 배열이다.

먼저 배경인 흰 도화지가 100x100이므로 도화지가 전부 채워진다면 색종이들의 넓이 합은 10000이 될 것이다.

100 x 100인 정사각형으로 구성되어 있는 도화지라고 생각하면서 풀이를 접근한다.

도화지에 색종이가 올려지면 해당 위치는 1로 바뀐다. 최종적으로는 1의 개수를 출력한다.

 

1. 요소가 0으로 초기화되어 있는 100 x 100 2차원 배열을 선언한다

 

2. 이중 for문을 사용하여 입력받은 x, y 좌표을 시작으로 10칸씩 위아래로 탐색한다.

    배열의 인덱스는 0부터 시작하기 때문에 탐색 시 x, y값에서 1씩을 뺀 인덱스를 탐색한다.

 

3. 탐색시 해당 배열의 요소가 0인 경우에만 그 값을 1로 바꾸고 sum값을 1 증가시킨다.

     이러면 중복된 x, y가 주어져도 이미 1로 칠해져 있기 때문에 그냥 넘어간다.

 

4. sum을 출력한다.

 

3. C++ 정답코드

#include <iostream>
using namespace std;

int main()
{
    const int SIZE = 10; //정사각형 색종이 한변의 길이 상수로 선언
    int x, y, n, sum = 0;
    int paper[100][100] = {0};
    cin >> n;
    while(n--)
    {
        cin >> x >> y;
        for (int i = x - 1; i < x + SIZE - 1; i++){
            for (int j = y - 1; j < y + SIZE - 1; j++){
                if (paper[i][j] == 0)
                {
                    paper[i][j] = 1;
                    sum++;
                }    
            }
        }
    }
    cout << sum;
    return 0;
}