백준 2653 - 파이썬

https://www.acmicpc.net/problem/2563

2563번: 색종이

문제 풀이

첨에 생각한 문제풀이 방식은 색종이 하나의 넓이는 100이기 때문에 '색종이의 총 개수 x 100 - 겹친 부분의 넓이' 이렇게 구하려고 하였다. 

n = int(input())

x_list = []
y_list = []

x = 0
y = 0

for _ in range(n):
  a, b = map(int,input().split())
  x_list.append((a,a+10))
  y_list.append((b,b+10))

for i in range(1,len(x_list)):
  if x_list[0][1] <= x_list[i][0]:
    continue
  else:
    x = abs(x_list[0][1] - x_list[i][0])

for i in range(1,len(y_list)):
  if y_list[0][1] <= y_list[i][1]:
    continue
  else:
    y = abs(y_list[0][1] - y_list[i][1])
  
print(100 * n - x*y)

하지만 이 방식은 다른 예제 입력이 들어왔을 경우 원하는 값이 나오지 않았고, 생각해야 하는 경우의 수가 너무 많아 코드로 구현하기가 힘들었다. 1시간쯤 고민하다가 구글링을 하였는데 전혀 생각하지도 못한 방법인데 코드로는 구현하기 쉬운 풀이가 있었다.

 

해당 방법은 몬테카를로 적분법의 아이디어를 빌린 것인데, 도화지의 크기는 가로, 세로의 크기가 각각 100으로 한정되어 있고, 색종이 넓이가 100이라는 뜻은 가로,세로의 길이가 각각 1인 정사각형이 100개 있다는 뜻이기도 하다. 이 점을 이용해서 도화지에 붙인 색종이의 총 넓이를 구했다.

 

n = int(input())
arr = [[0] * 100 for _ in range(100)]

result = 0
for _ in range(n):
  a,b = map(int,input().split())
  for i in range(a,a+10):
    for j in range(b,b+10):
      if arr[i][j] != 1:
        arr[i][j] = 1
        result += 1

print(result)

구글링시 다른 사람들의 경우 이중 for문을 한번 더 사용하여 1의 개수를 셌는데, 나는 어차피 1로 변환할때 총 넓이도 1증가하는 것이기 때문에 함께 계산해 줬다.

 

느낀점

실버 5문제를 못풀고 있어서 슬퍼하고 있었는데, 몬테카를로 적분법의 아이디어를 이용해야 간단한 문제였다. 이번 문제를 풀면서 몬테카를로의 적분법도 공부할 수 있어 좋았고, 넓이 구하는 문제들은 이 적분법을 이용하면 간단하게 풀 수 있을거 같다.