[백준 2563][C++] 색종이

문제 링크

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

2563번: 색종이

---

◆문제 해결 및 설명◆

문제 해설 : 100x100 도화지에 10x10 색종이들을 붙이고  도화지가 가려진 넓이를 출력하여라.

 

두가지 방법이 떠올랐는데, 좌표를 사용하여 마지막 결과값을 계산하기와 이차원 배열을 구현하여 직접 칠하는 방법이 떠올랐다. 하지만 색종이가 최대 100장이나 되는데 이를 비교하는것이 직접 칠하는것보다 시간복잡도 측면에서 효율적이지 않다고 생각하고 구현이 복잡함으로 직접 칠하는 방법으로 코드를 작성하였다.

 

간단한 코드임으로 짧게 글로 설명하겠다. 2차원 배열 whiteBoard를 선언해주고 색종이를 받아서 해당 위치를 1로 초기화해준다. 모든 색종이에 대한 연산이 끝났다면 whiteBoard의 1의 갯수를 계산하여 정답으로 출력해준다.

 

코드가 너저분해보여 algorithm의 fill을 사용한 버전도 코드에 올려놓겠다. #1 부분을 삭제하고 주석을 코드로 돌려주면 된다.

 

◆코드 전문◆

#include <iostream>
#include <vector>
// #include <algorithm>

using namespace std;

int main()
{
    vector<vector<int>> whiteBoard(105, vector<int>(105));
    int numOfColoredPaper;
    cin >> numOfColoredPaper;
    while (numOfColoredPaper--)
    {
        int row, col;
        cin >> row >> col;
        for (int i = row; i < row + 10; i++)
        {
            // #1
            for (int j = col; j < col + 10; j++)
            {
                if (!whiteBoard[i][j])
                {
                    whiteBoard[i][j] = 1;
                }
            }

            // #2
            // fill(&whiteBoard[i][col], &whiteBoard[i][col] + 10, 1);
        }
    }

    int answer = 0;
    for (int i = 0; i < whiteBoard.size(); i++)
    {
        for (int j = 0; j < whiteBoard[i].size(); j++)
        {
            answer += whiteBoard[i][j];
        }
    }
    cout << answer;
}