백준 1531 - 투명

문제

알고리즘 분류)

• 구현
• 시뮬레이션

풀이

일단 문제를 보자마자 2차원 배열에 100*100의 행렬을 찍었다.
그리곤 문제를 어떻게 풀지 고민하였다.
보자마자 거의 생각이 들었다. 입력되는 x1,y1,x2,y2의 좌표를 바탕으로 해당하는 구역내의
원소의 값을 1씩 증가시키면 종이가 깔리는 것과 비슷할 것이고,
겹치는 부분은 알아서 2...3... 이런식으로 증가할 것이다.

좌표 설정에 있어서 헷갈림이 많았다.
x1, y1, x2, y2 가 21, 21, 80, 80 이라고 가정하자

왼쪽 아래 모서리의 x좌표 : x1-1
0에서 x1만큼 오른쪽으로 가주어야 하는데, (1, 1)은 실제로는 배열의 (0, 0)에 해당하므로 -1을 해준다
왼쪽 아래 모서리의 y좌표 : 100-y1+1
아래에서 y1만큼 올라온 좌표를 문제에선 제시하였는데 그것은 배열에서 100-y1+1만큼 내려간좌표이다
100-y2 부터 100-y1까지 for문을 돌 것인데 파이썬은 마지막 정수를 포함하지 않으므로 +1로 포함시켜준다
오른쪽 위 모서리의 x좌표 : x2
0에서 x2만큼 오른쪽으로 가준 좌표이다
x1-1 부터 x2까지 for문을 돈다
오른쪽 위 모서리의 y좌표 : 100-y2
마찬가지로 y2만큼 올라온 좌표는 배열에서 100-y2만큼 내려간 좌표이다

종이의 좌표는 이렇게 설정해주고 문제에서는 M이 주어지는데 M개 이하의 종이가 올려져있으면 그림이 보인다
-> 즉, M+1개의 종이가 올려지면 보이지 않는다

100*100의 배열을 생성할 때, 모든 원소를 M으로 설정해주고
종이를 덮을 때 마다 -1 씩 해주어
종이가 음수가된 부분을 카운트해준다

소스코드

python)

N,M = map(int,input().split())
array = [[M for col in range(100)] for row in range(100)]

for i in range(N):
    x1,y1,x2,y2 = map(int,input().split())
    for y in range(100-y2,100-y1+1):
        for x in range(x1-1,x2):
            array[y][x] -= 1
            
total = 0
for i in range(100):
    for j in range(100):
        if array[i][j] < 0:
            total += 1
    
print(total)