백준 2563 번 문제 풀이 Python 파이썬 :색종이

#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.

코드편집/실행

S = [[0]*100 for _ in range(100)]
# 도화지 리스트. 100 x 100 2차원 배열, 0으로 초기화
N = int(input())
# 숫자를 입력받아 정수형으로 변환해서 색종이 수 N 에 대입.
for _ in range(N): # 주어진 색종이 개수만큼 루프
  x, y = map(int, input().split())
  # 색종이 좌표 값을 받아서 정수형으로 변환해서 x, y에 대입 
  for i in range(x, x + 10): # x 축으로 10칸
    for j in range(y, y + 10): # y 축으로 10칸
      S[i][j] = 1 # 색종로 채워짐

# 색종이를 모두 붙였으면, 면적을 계산(배열값이 1인 개수)
sum = 0 # 면적, 초기값 0
for i in range(100): # 도화지 가로크기
  for j in range(100): # 도화지 세로크기
    if S[i][j] == 1: 
      sum += 1 # 배열이 1값이면 면적 더함

print(sum) # 색종이가 붙은 배열개수(면적) 출력