백준 2563번

백준 2563번

 

처음에는 100*N에서 겹친 만큼의 넓이를 빼는 방식으로 접근했고 다음과 같이 작성하였다.

 

(사실 색종이가 겹치는 경우에 대한 조건과 겹친 만큼의 넓이를 구하는 식을 일반화하는 데도 시간이 걸렸다.)

import sys

N = int(sys.stdin.readline())

papers = []

for i in range(N):
    paper = list(map(int, sys.stdin.readline().split()))
    papers.append(paper)

overlappedArea = 0

for i in range(N-1):
    for j in range(i+1, N):
        if 10-abs(papers[i][0]-papers[j][0]) > 0 and 10-abs(papers[i][1]-papers[j][1]) > 0 :
            overlappedArea += (10-abs(papers[i][0]-papers[j][0])) * (10-abs(papers[i][1]-papers[j][1]))

totalArea = 100 * N - overlappedArea

print(totalArea)

 

문제에 주어진 예시에 대해서는 정답을 출력해냈는데 제출해보니 틀렸습니다가 나왔다.

 

다시 생각해보니 겹치는 부분들이 전부 오직 두 개의 색종이에 의한 것일 때만 유효하고,

 

겹치는 부분들이 세 개 이상의 색종이에 의한 것일 경우 겹친 면적을 중복하여 빼게 되는 것이다.

 

고민해보다가 잘 모르겠어서 답을 찾아봤다.

import sys

N = int(sys.stdin.readline())

area = [[0 for col in range(100)] for row in range(100)]

for n in range(N):
    x, y = map(int, sys.stdin.readline().split())

    for i in range(10):
        for j in range(10):
            area[x+i][y+j] = 1

totalArea = 0

for i in range(100):
    for j in range(100):
        totalArea += area[i][j]

print(totalArea)

 

100*100의 도화지를 1*1의 격자들로 쪼개고 색종이가 놓인 격자엔 1, 아닌 격자엔 0을 할당해 모든 격자의 값을 더한다.

 

새로운 관점을 배웠다!