백준 10163번 색종이 [C언어]

문제 출처: https://www.acmicpc.net/problem/10163

10163번: 색종이

 

 

Sol)

#include <stdio.h>

typedef struct{
    int x;
    int y;
    int width;
    int height;
} paper; //색종이 하나의 왼쪽 아래 꼭짓점의 좌표와 크기를 저장할 구조체

int main()
{
    int grid[1001][1001] = {0}; //색종이가 놓여질 판. 최대 1001 * 1001
    int N; //종이 개수

    scanf("%d", &N);

    paper p[N]; //구조체 배열 선언

    for(int i = 0; i < N; i++){
        scanf("%d %d %d %d", &p[i].x, &p[i].y, &p[i].width, &p[i].height);

        for(int k = p[i].y; k < p[i].y + p[i].height; k++){
            for(int j = p[i].x; j < p[i].x + p[i].width; j++){ //입력받은 수로 색종이가 놓여진 곳 표시
                grid[k][j] = i + 1;
            }
        }
    }

    for(int i = 0; i < N; i++){
        int  cnt = 0;

        for(int k = p[i].y; k < p[i].y + p[i].height; k++){
            for(int j = p[i].x; j < p[i].x + p[i].width; j++){
                if(grid[k][j] == i + 1) //색종이의 크기만큼 검사하며 가려진 부분을 제외한 부분을 셈
                    cnt++;
            }
        }
        printf("%d\n", cnt);
    }

    return 0;
}

 

• 풀이 방향

단순히 색종이들의 면적 자체를 구하는 것은 전혀 어렵지 않다. 관건은 겹치는 부분을 어떻게 처리하느냐이다. 배열을 사용하지 않으면 색종이가 여러장 들어왔을 때 상황이 너무 복잡해질 수 있다. 따라서, 전체 보드판 배열을 하나 선언 해 주고, 들어오는 색종이에 번호를 매겨 색종이의 좌표와 크기에 따라 해당 색종이의 번호를 보드 판의 좌표에 할당해 주면 될 것 같다. 이렇게 하면 겹치는 부분이 생기는 경우 그냥 숫자를 덧씌우면 되기때문에 복잡하게 케이스를 나눌 필요가 없다. 이 방법의 시간 복잡도는 색종이의 개수 만큼 for 문을 돌려야 해서 O(N) 하나, 그리고 그 안 쪽에 색종이의 가로세로 크기에 따라 반복되는 2중 for문 O(width*height) 하나 해서 총 O(N*width*height) 이 나오지만, 각각이 최대값으로 들어와도 N*width*height 의 값은 1억 정도라서 제한시간 1초안에 얼추 들어올 것이다.

 

• 풀이

색종이가 놓여질 판을 최대 가로세로 크기에 맞춰 선언한다. 그 후 색종이의 시작 위치부터 가로, 세로 값에 맞춰 0으로 초기화된 전체 판 배열에 색종이가 들어온 순번과 대응되는 숫자를 할당한다.

색종이의 면적을 출력할 때도 해당 색종이의 시작 위치부터 해당 색종이가 들어온 순서에 대응되는 수가 몇개냐로 면적을 구한다.

 

• 문제에 대한 사견

다른 사람들은 어떻게 풀었는지 보기 위해 검색해 본 결과 틀린 답이 굉장히 많았다. 특히, 전체 판의 크기를 1001 * 1001이 아닌 101 * 101 로 선언한 경우가 많았다. 항상 문제 조건은 주의해서 확인하도록 하자.