백준 2563 번 문제 풀이 C++ :색종이

#72. 백준 2563번 문제 풀이: 색종이

가로, 세로 크기가 100, 100 인 도화지가 있다. 이 도화지에 가로,세로 10, 10 인 색종이를 도화지의 변과 평형하게 붙인다. 이런 방식으로 색종이를 한 장 이상 붙인 후 색종이가 붙은 영역의 넓이를 구하는 프로그램을 작성하시오. 입력: 첫 줄에 색종이 수, 둘째 줄 부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이의 위치는 두개의 자연수로 주어지는데 도화지의 왼쪽변과 아래쪽 변과의 거리이다. 색종이 수는 100 이하, 색종이가 도화지 밖으로 나가는 경우는 없다. 출력: 색종이가 붙은 영역의 넓이를 출력

입력/출력

--입력--
3
3 7
15 7
5 2
--출력--
260

문제풀이+해설

일반적으로 생각하면 색종이 하나의 넓이는 10x10=100 이고,
겹쳐지게 색종이를 붙인다면 100 + 100 -(겹친부분 넓이) 를 해서 계산할 것이다.
세번째 색종이가 첫번째 두번째 모두와 일부 겹쳐지게 붙인다면? ..계산이 복잡해 진다.

일반적인 수학적인 방법이 아닌 다른 알고리즘을 생각해 보자.
도화지 크기가 100 x 100 이라 했고, 색종이가 10 x 10 이라고 했다.
이것을 배열이라고 생각하고 풀어보자.
100 x 100 의 0값으로 채워진 배열(도화지)에 10 x 10 의 값들(색종이)은 1로 채우자.
결국 여러장의 색종이가 겹치는 것과 상관없이, 배열값이 1 인 값들의 합이 색종이가 붙은 면적이 된다.
아래 그림처럼 도화지 사각형에 1로된 색종이들이 겹쳐있더라도, 겹침과 상관없이 1로 체크된 부분을 채워진 면적으로 볼 수 있다.
  ---------
 |   1111  |   
 | 111111  |
 | 111111  |
 | 1111    |
  ---------

code sol.

코드편집/실행

#include <iostream>
using namespace std;

int main() {
  int i, j, k, x, y, sum, N;
  int S[100][100] = {0};
  // 도화지 리스트. 100 x 100 2차원 배열, 0으로 초기화
  cin >> N;
  // 숫자를 입력받아 정수형으로 변환해서 색종이 수 N 에 대입.
  for(k = 0; k < N; k++) { // 주어진 색종이 개수만큼 루프
    cin >> x >> y; // 색종이 좌표 값을 x, y에 대입 
    for(i = 0; i < 10; i++) { // x 축으로 10칸
      for(j = 0; j < 10; j++) { // y 축으로 10칸
        S[x + i][y + j] = 1; // 색종로 채워짐
      }
    }
  }
  // 색종이를 모두 붙였으면, 면적을 계산(배열값이 1인 개수)
  sum = 0; // 면적, 초기값 0
  for(i = 0; i < 100; i++) // 도화지 가로크기
    for(j = 0; j < 100; j++) // 도화지 세로크기
      if(S[i][j] == 1) sum += 1; // 배열이 1값이면 면적 더함

  cout << sum; // 색종이가 붙은 배열개수(면적) 출력
  return 0;
}