[백준][분할정복] 퍼즐 자르기

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

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

14727번: 퍼즐 자르기

 

내가 작성한 코드

import sys
from collections import defaultdict
read = sys.stdin.readline

def find(group, i):
    if group[i] == -1:
        return -1
    elif group[i] == i:
        return i
    group[i] = find(group, group[i])
    return group[i]

def union(group, x, y):
    group_x = find(group,x)
    group_y = find(group,y)
    if group_x < group_y:
        group[y] = group_x
    else:
        group[x] = group_y

N = int(read().rstrip())
nums = []
for _ in range(N):
    nums.append(int(read().rstrip()))

group = [-1 for i in range(N)]
all = defaultdict(list)
mx = 0
for i, num in sorted(enumerate(nums), reverse=True, key=lambda x: x[1]):
    group[i] = i
    all[i] = [num, 1]
    if i + 1 < N and find(group, i + 1) != -1:
        union(group, i, i+1)
        all[i][0] = min(all[i][0], all[i+1][0])
        all[i][1] += all[i+1][1]
    if i - 1 >= 0 and find(group, i - 1) != -1:
        grp_left = find(group,i-1)
        union(group, i-1, i)
        all[grp_left][0] = min(all[i][0], all[grp_left][0])
        all[grp_left][1] += all[i][1]
    grp = find(group, i)
    mx = max(mx, all[grp][0] * all[grp][1])

print(mx)

• 최대값부터 순차 탐색
  
  • 정렬 전 인덱스도 함께 저장
• 인덱스로 인접한 직사각형 확인
  • 유니온파인드 사용

 

다른 사람이 작성한 코드

None

 

기억해야할 것

• 시간초과를 많이 함
  
  • 매 loop마다 min * len을 계산해서 max를 계산하니 시간초과
  • min과 len을 저장하는 방식으로 변경