[Algorithm🧬] 백준 2457 : 공주님의 정원

문제

시간초과

DFS 로 접근했다.

입력은 1월 1일 -> 1, 12월 31일 -> 365 로 만들 수 있게 바꾸어줌.
일단 넣어도 공주 범위를 만들 수 없는거 애초에 빼고 시작하고,
시작 날짜가 같다면 더 늦게 지는 꽃만 가지고 시작함.

그래서 처음 넣는 꽃이면 s, e 갱신
이미 꽃 넣었는데 그 꽃이랑 기간이 이어질 수 있다면 end 만 갱신

모든 경우에 해당 꽃을 선택해보지 않는 경우

를 해서 돌렸는데 테케에 대한 답은 잘 나오나 시간 초과가 남.. 이렇게는 하기 힘들듯.

import sys
sys.setrecursionlimit(10 ** 6)
readl = sys.stdin.readline

def check(start, end):
    if start <= always[0] and always[1] < end:
        return True
    return False


def DFS(level, cnt, start, end):
# def DFS(level, cnt):
    global min_cnt
    if cnt > min_cnt:
        return

    if start > always[0]:
        return


    # 하다가 중간에 이미 범위가 맞으면 더 해 볼 필요 없음.
    if end >= always[1]:
        if check(start, end):
            if min_cnt > cnt:
                min_cnt = cnt
            return

    if level == len(flower):
        return

    s, e = flower[level]
    
    # 이번에 처음 들어감 -> start 갱신 필요.
    if cnt == 0:
        DFS(level + 1, cnt + 1, s, e)
    # 처음 들어가는게 아니면 이전 start 로 유지.
    # 어차피 Start 기준으로 정렬해놔서 새로 구간을 추가한다고 해서
    # start 가 갱신될 일은 없음.
    elif s <= end < e:
        DFS(level + 1, cnt + 1, start, e)
    
    # 안들어감.
    DFS(level + 1, cnt, start, end)

    

days = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
N = int(readl())

always = (sum(days[:3]) + 1, sum(days[:11]) + 30) # 항상 피어있어야 하는 구간.

# 입력 가공. -> 1월 1일 -> 1
# 2월 1일 -> 32 가 될 수 있게.
flower = []
for _ in range(N):
    sm, sd, em, ed = map(int, readl().split())
    start = sum(days[:sm]) + sd
    end = sum(days[:em]) + ed
    
    # 공주 기간보다 앞에서 끝나거나 뒤에서 시작하는건 아예 빼고 시작.
    if end < always[0] or always[1] < start:
        continue

    flower.append((start, end))

# 시작 날짜 기준 정렬을 하는데,
# 시작 날짜가 같으면 끝나는 시간이 더 긴게 먼저 오도록 가공.
flower.sort(key=lambda x: 400 * x[0] - x[1])

newflower = [flower[0]]
start = 0
for i in range(1, len(flower)):
    if flower[start][0] == flower[i][0]:
        continue
    start = i
    newflower.append(flower[start])
    
flower = newflower
# print(flower)


min_cnt = 200000
res = [0] * N
# DFS(0, 0)
DFS(0, 0, 0, 0)
print(min_cnt)

Greedy

참고 https://velog.io/@eunsung-dev/백준-2457-공주님의-정원

지는 날짜 순서대로 정렬을 하고,
시작하는 날짜가 지금까지 지정한 끝나는 날짜보다 앞쪽이면서 지는 날짜가 더 큰 것을 고른다.

import sys
readl = sys.stdin.readline

days = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
N = int(readl())

always = (sum(days[:3]) + 1, sum(days[:11]) + 30 + 1) # 항상 피어있어야 하는 구간.

# 입력 가공. -> 1월 1일 -> 1
# 2월 1일 -> 32 가 될 수 있게.
flower = []
min_start = 400
max_end = 0
for _ in range(N):
    sm, sd, em, ed = map(int, readl().split())
    start = sum(days[:sm]) + sd
    end = sum(days[:em]) + ed
    
    # 공주 기간보다 앞에서 끝나거나 뒤에서 시작하는건 아예 빼고 시작.
    if end < always[0] or always[1] < start:
        continue

    min_start = min(min_start, start)
    max_end = max(max_end, end)

    flower.append((start, end))

# 못만들면 처음부터 끝내고 시작!!
if min_start > always[0] or max_end < always[1]:
    print(0)
    exit(0)

# 시작 날짜 기준 정렬을 하는데,
# 시작 날짜가 같으면 끝나는 시간이 더 긴게 먼저 오도록 가공.
flower.sort(key=lambda x:x[0])

cnt = 0

t = always[0]
while t < always[1]:
    next_t = t
    for i in range(len(flower)):
        # 시작하는 시간이 지금 시각보다 앞이면서
        # 끝나는 시간이 가장 큰거.
        if flower[i][0] <= t and flower[i][1] > next_t:
            next_t = flower[i][1]
    
    if next_t == t:
        cnt = 0
        break
    
    cnt += 1
    t = next_t

print(cnt)

아래처럼도 바꿀 수 있음!!

t = always[0]
i = 0
while t < always[1]:
    max_e = 0

    while i < len(flower) and flower[i][0] <= t:
        max_e = max(max_e, flower[i][1])
        i += 1
    
    if max_e == t:
        cnt = 0
        break
    
    cnt += 1
    # t = next_t
    t = max_e

print(cnt)