실력키우기 색종이(초)(C++)

1438 : 색종이(초)

제한시간: 1000 ms    메모리제한: 32 MB
해결횟수: 1120 회    시도횟수: 1959 회   

가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오.

 

 

 

예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 그림과 같은 모양으로 붙였다면 검은색 영역의 넓이는 260이 된다.

 

첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다.
색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고, 두 번째 자연수는 색종이의 아래쪽 변과 도화지의 아래쪽 변 사이의 거리이다.

색종이의 수는 100 이하이며, 색종이가 도화지 밖으로 나가는 경우는 없다.

첫째 줄에 색종이가 붙은 검은 영역의 넓이를 출력한다.

[Copy] 3 3 7 15 7 5 2

[Copy] 260

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

/**************************************************************     Problem: 1438     User: a132034     Language: C++     Result: Success     Time:0 ms     Memory:1140 kb ****************************************************************/     #include    <cstdio> #pragma warning(disable:4996) int paper[111][111]; int main() {     int n;     scanf("%d", &n);     int sx, sy;     for (int i = 0; i < n; ++i)     {         scanf("%d%d", &sx, &sy);         for (int x = sx; x < sx + 10; ++x)         for (int y = sy; y < sy + 10; ++y)             paper[x][y] = 1;     }     int res = 0;     for (int i = 1; i <= 100; ++i)     for (int j = 1; j <= 100; ++j)     if (paper[i][j] == 1)res++;     printf("%d", res);       return 0; }

만약 색종이가 매우 많거나 도화지가 매우 크거나 했다면 이런 방법이 아닌 라인스위핑을 사용해야 했을 것 같지만... 

다행이도 배열로 만들만 한 범위내에 있었기 때문에 배열로 입력받은 점부터 10 x 10의 사각형범위에 모두 1을 해 주었다. 

모든 값을 입력받은 후에는 전체를 탐색하면서 1인 배열의 위치를 찾을때마다 넓이를 1씩 추가해주었다.