[Algorithm🧬] 백준 2517 : 색종이 - 3

문제

처음에 생각한거

가로로 이을 수 있을 때 까지 잇고
세로는 그 때 겹치는 부분의 길이

-> 끊어지면 거기서부터 다시 구해서 배열에 넣어놓고 가로 최댓값 찾음.

반례) 색종이-2 처럼 안끊어지고 다 이어져있으면요..? 근데 또 이어져는 있는데 두개씩만 이어져 있음
-> 그러면 가로에서 두개 세로에서 두개 찾아서 비교해야되는데 이 코드로 하면 그건 안됨...

import sys

readl = sys.stdin.readline


def 직사각형(색종이):
    # 지금까지 색종이 붙여서 가로 최대 -> 거기에 들어온 색종이의 세로 최소 or
    # 지금까지 색종이 붙여서 세로 최대 -> 거기에 들어온 색종이의 가로 최소
    # 중 최댓값

    색종이.sort()

    arr = []

    # arr2 = []

    start_x, start_y = 색종이[0]
    end_x, end_y = map(lambda x: x + 10, 색종이[0])

    for sx, sy in 색종이:
        ex = sx + 10
        ey = sy + 10

        # 가로는 이을 수 있다면 계속 이어줌
        if sx <= end_x:

            # 가로가 이어졌을 때 세로는 줄어들어야 함.
            # 이전에 붙어있는게 지금거보다 y축 기준 아래에 있으면 위의 if
            # 지금거보다 y 축 기준 위에 있으면 아래의 if
            if start_y <= sy < end_y:
                start_y = sy
                end_x = ex
            elif start_y < ey <= end_y:
                end_y = ey
                end_x = ex
            # else: # 둘 다 만족이 안되면 두 영역이 안겹치고 완전 바깥에 있는거니까 가로도 이으면 안됨.

        else:
            # 가로를 이을 수 없다면 일단 배열에 저장.
            # arr2.append(((start_x, end_x), (start_y, end_y)))
            arr.append((end_x - start_x, end_y - start_y))
            start_x = sx
            end_x = ex
            start_y = sy
            end_y = ey

    # arr2.append(((start_x, end_x), (start_y, end_y)))
    arr.append((end_x - start_x, end_y - start_y))

    # print(arr2)

    max_width, height = max(arr)

    return max_width * height


n = int(readl())
색종이 = [list(map(int, readl().split())) for _ in range(n)]

# 가로가 제일 긴거
candidate = 직사각형(색종이)


# 세로가 제일 긴거
색종이 = list(map(lambda x:[x[1], x[0]], 색종이))
candidate = max(candidate, 직사각형(색종이))


print(candidate)

아무리 생각해도 저렇게는 답이 안나와서.

참고 하여 풀었다. 원리를 이해하니까 코드도 바로 이해되는 문제.

import sys

readl = sys.stdin.readline

n = int(readl())

도화지 = [[0] * 100 for _ in range(100)]

for _ in range(n):
    r, c = map(int, readl().split())
    r -= 1
    c -= 1
    for i in range(r, r + 10):
        for j in range(c, c + 10):
            도화지[i][j] = 1


# 높이에 대한 누적합으로 색종이 붙인 곳을 채워두고
for i in range(1, 100):
    for j in range(100):
        if 도화지[i][j] == 1:
            도화지[i][j] = 도화지[i - 1][j] + 1


size = 0
max_size = 0

# 점 하나를 선택해서,
for row in range(100):
    for sw in range(100):
        if 도화지[row][sw] == 0:
            continue
        # 그 점부터 오른쪽으로 쭉 가면서 width 를 늘린다.
        height = 101

        for idx in range(sw, 100):
            # 그리고 해당 지점에 써있는 가장 작은 값이 height 가 됨.
            h = min(height, 도화지[row][idx])
            if height == 0:
                break
            size = height * (idx - sw + 1)
            max_size = max(max_size, size)

print(max_size)