[C++] 백준 2563번 풀이 ( 색종이 )

- 문제 (2563번) : 색종이

• 링크 : https://www.acmicpc.net/problem/2563

• 100 x 100 크기의 도화지에 10 x 10 크기의 색종이를 붙이는데 이때 색종이를 붙인 영역의 넓이를 구하는 문제.
  • 색종이는 100 x 100 크기의 도화지를 넘는 일은 없고, 색종이끼리 겹치는 경우는 존재함.

---

- 입력 및 출력

[ 입력 ]

• 첫째 줄에 붙일 색종이의 수를 입력. ( n )
• 두번째 줄부터 n번만큼 ( 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리, 색종이의 아래쪽 변과 도화지의 아래쪽 변 사이의 거리 ) 를 입력받는다.

  • ex) 3 7 을 입력받았다면
    색종이는 3~12, 7~16 위치에 붙음.

[ 출력 ]

• 색종이가 붙은 영역의 넓이를 출력.

---

- 문제 풀이

• 나는 처음에 아래와 같이 문제에 접근하였다.

  1. 붙일 색종이의 왼쪽, 오른쪽, 위, 아래의 좌표를 각각의 배열에 저장한다.
  2. 입력을 하나씩 받으며 area 를 계산하고, 위에서 좌표를 각각 배열에 저장했으니, 겹치는 부분을 빼며 area 를 계산하고자 하였다.

• 하지만 위와 같이 접근을 하는 경우 구현할 방법이 떠오르지도 않았고, 어찌저찌 구현을 했더라도 효율이 매우 좋지 않았을 것 같다.

• 그래서 나는 방법을 바꿔 다시 접근하였다.

  1. 주어진 도화지의 size 는 100 x 100 크기로 고정되어있었고, 붙이는 색종이는 도화지를 넘어갈 수 없다는 제약이 있으므로, 도화지를 2차원 배열로 고정시켜놓았다. ( 값은 0으로 초기화 )
     ( 영상처리에서 2D image 를 2차원 배열로 사용하는 것처럼 )
  2. 그 후 색종이가 붙는 위치의 값을 1로 변환시켜주었다.
  3. 입력 process 와 출력 process 를 나눠 진행시켰는데, 위와 같이 배열의 값을 설정했다면, 100 x 100 size 의 배열을 쭉 돌면서 배열의 총 합을 구한다면, 이것이 바로 색종이가 붙은 영역의 크기라고 생각했다.

• 위와 같은 방법으로 코드를 구현해보았다.

  1. [ 도화지를 2차원 배열로 생성 ]

  	int store[100][100] = {0, };

  • 이 때 0으로 무조건 초기화를 해주어야함.
    ( 초기화 안하면 쓰레기값이 들어가져있어 나중에 문제가 될 수 있음 )

  2. [ 색종이가 붙는 위치의 값을 1로 변경 ]

     for(int i = 0; i < n; i++) {
            int a, b = 0;
            std::cin >> a >> b;
            for(int j = a-1; j < a + 9; j++) {
                for(int k = b - 1; k < b + 9; k++) {
                    store[j][k] = 1;
                }
            }
        }

  • 10 x 10 크기의 색종이이므로, 가로 10번, 세로 10번 총 100번을 돌며 그 index 의 값을 1로 설정.
    ( 이 외의 값은 0임. )

  3. [ 색종이가 붙은 크기 구하기 ]

  int sum = 0; /* store area */
      for(int i = 0; i < 100; i++) {
          for (int j = 0; j < 100; j++) {
              sum += store[i][j];
          }
      }

  • 도화지의 모든 크기를 돌며 배열의 값을 더하기.
  • 각 index 에 붙어있는 색종이의 size 는 1이고, 그 index 의 값이 1이므로, 도화지 배열에 있는 값을 모두 더한 값이 도화지에 붙은 색종이의 넓이가 된다.

---

- 최종 코드