문제

BOJ 2571: 색종이 - 3 https://www.acmicpc.net/problem/2571

풀이

조건

• 검은색 색종이의 수와 각 색종이를 붙인 위치가 주어질 때 잘라낼 수 있는 검은색 직사각형의 최대 넓이를 구한다.

풀이 순서

• 종이가 붙는 위치를 모두 1로 초기화한다.
• 종이가 붙은 위치만 위에서 아래로 누적합을 구한다.
  • 해당 위치의 값이 사각형의 세로 길이가 된다.
• 모든 위치를 탐색하며 종이가 있는 위치인지 탐색한다.
  • 해당 위치에서 가로로 탐색한다.
  • 가로로 탐색한 위치의 값이 0이라면 종이가 없는 위치이기 때문에 다음으로 넘어간다.
  • 값이 있다면 해당 가로 위치의 값 중 최소값을 구한다.
    • 사각형의 높이가 바뀌었기 때문
  • 사각형의 넓이를 구한다.

코드

Python

board = [[0 for _ in range(110)] for _ in range(110)]

N = int(input())

# 위치 찍어놓기
for _ in range(N):
    a, b = map(int, input().split())

    for i in range(a, a + 10):
        for j in range(b, b + 10):
            board[i][j] = 1

# 세로로 누적합 구하기
# --> 각 지점의 값이 각 지점의 세로 높이와 같아진다
for i in range(99):
    for j in range(100):
        if board[i][j] != 0 and board[i + 1][j] != 0:
            board[i + 1][j] = board[i][j] + 1

answer = 0
for i in range(100):
    for j in range(100):
        h = 100
        # 현재 위치를 기준으로 오른쪽만 보면서 가능한 높이를 구하고
        # 구한 높이를 통해 사각형의 넓이를 구한다
        for k in range(j, 100):
            h = min(h, board[i][k])
            if h == 0:
                break
            # 사각형 넓이 구하기
            answer = max(answer, h * (k - j + 1))

print(answer)

정리

• 누적합을 구하는 것 까진 알아냈지만 해당 값을 제대로 이용하지 못했다.