2457 - 공주님의 정원 (Greedy 자력솔하기)

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

2457번: 공주님의 정원

 

원트에 자력솔 성공했다! 채점 돌아갈 때 심장이 넘 떨렸다... 내가 구현을 깔끔하게 잘 못짜는 편이라 코드가 너무 길어지기도 했고 내가 생각한대로 딱! 구현하려다보니 뭔가 꽉 막힌 구현이 된 것 같다.

어제 알고리즘 캠프에서 그리디를 배워서 오늘 그리디 문제를 뒤적거리다가 전에 누가 추천해준 문제이기도 하고, 어제 푼 난이도랑 비슷할 것 같아서 골랐다. 

그리디 접근 방식을 연습하려고 잡은 문제인데 갑자기 재밌어져서 집중해서 구현까지 완료했다. 질문 게시판에 반례도 잘 나와있어서 부등호 처리까지 깔끔하게 해주면 된다. (반례 참고 : https://www.acmicpc.net/board/view/86573)

나름대로 발상과 접근을 적어보았다.

---

우선 문제에서는 꽃의 피는 기간 list를 주고, 꽃이 최소 개수로 피면서 3/1 ~ 11/30 까지 피어있는 상태를 원한다.

여기서 간단하게 생각해 볼 점?

1) 꽃 피는 기간이 겹칠 수 있고, 기간이 긴 꽃은 다른 여러 꽃과 겹친다. 특히, 어느 긴 구간 안에 다른 짧은 구간이 겹쳐있는 것은 비효율적인 선택이다.

2) 꽃 피는 기간이 너무 짧으면 전 기간을 다 못 채울 수도 있다.

---

 

다양한 접근을 해봤다.

1) 기간이 긴 순으로 정렬하여 세그 배치해보기 -> X (너무 쉬운 반례가 있음)

2) 기간이 일찍 시작 or 늦게 끝나는 순서로 정렬해보기 (회의실 문제처럼) -> X (한 쪽만 중요한 게 아니라 양 끝점 다 중요)

 

3) ANS 집합의 OPT 하나를 가정하고, 이전보다 나쁘지 않은 선택이 되려면 어떻게 조작해야 할지 생각하기

우리가 앞으로 걸게 될 구간은 1, 2, 3 모두 가능하다

특정 꽃 집합으로부터, 3/1 ~ 11/30 까지 피어있을 수 있는 정해를 하나 들고왔다고 가정하자. 정해에서 최소 꽃 개수가 N개 라고 치면, 그 전체 구간 중에서 일부인 그림 상의 구간을 관찰할 것이다. (임의로 딱 맞아떨어지게 그린 구간이다.)

순서대로 전체 N개의 구간 중에서 일부인 K-1 / K / K+1 번째 구간을 볼 건데, 우리는 N개의 최소 개수가 흐트러지지 않도록 하면서(= 한 구간에 다른 구간이 완전히 포함되면 안된다는 의미), Kth 구간을 조작해보는거다.

(1) K-1의 끝점보다 Kth 구간의 시작 점이 앞으로 가서 살짝 겹치는 형태가 될 수 있다. 이렇게 조작해도 답 N개는 그대로이다.

(2) K+1의 시작점보다 Kth 구간의 끝점이 더 멀리가는 형태가 될 수 있다. 일부 겹치더라도 답 N개는 그대로이다.

(3) 마지막으로, K-1의 끝점보다 K의 시작점이 더 앞에 있고, K+1의 시작점보다 K의 끝점이 더 뒤에 있을 수도 있다. (양 옆으로 겹치는 형태)

물론 문제에서는 끝점이 꽃이 지는 날짜이기 때문에 포함 관계/부등호를 잘 처리해줘야 하는데 그림 상으로는 간단하게 그렸다. (나중에 질문 게시판을 보니 이 부분에서 구현을 틀린 사람이 많아 보였다.)

 

---

 

그러면 이렇게 조작했을 때 우리가 알 수 있는건 뭘까?

우리는 Kth 구간을 어떻게 조작하든, 앞 구간의 끝나는 점을 포함해야하고 뒷 구간의 시작하는 점도 포함해야 한다. 위 그림을 문제에 적용하면, 문제에서 주어진 조건인  3/1 ~ 11/30 을 볼 때, 3/1 (앞 구간의 끝나는 점), 11/ 30 (뒷 구간의 시작점) 이렇게 대응할 수 있고, 구간을 이으면서 양 끝점을 모두 포함하거나 걸치는 선택을 해야 한다.

동시에 꽃 개수를 최소화 하기 위해서 무엇을 해야 할까?  앞에 붙일 구간을 [a, b) 라고 했을 때, 앞 구간의 끝 점 >= a 이면서, b가 제일 뒤에 있는 걸 고르는 거다. 그리고 이어 붙였으면 b가 다시 우리가 연결해야 하는 남은 구간의 시작점이 되도록 변경하면 된다. 왜냐하면 이러한 구간이 시작점을 포함하거나 걸치는 모든 구간들을 다 비교했을 때 나쁘지 않은 선택이기 때문이다.

또한, 앞부터 열심히 구간을 이어서 11/30 에 가까이 가고 있는데, 막상 마지막에 11/30을 포함하거나 걸치는 구간이 없을 수도 있다. 이러면 무조건 불가능한 케이스이다. 그래서 끝점인 (11/30)을 포함하는 구간이 있는지 확인해줘야 한다.

자력솔 한 후, 다른 풀이들을 봤는데 앞에서부터 하나씩 걸면서 끝점이 더 멀어지는 구간이 나오면  이전 것을 삭제하고/바꿔주고를 반복하는 것 같았다.

나는 이와 다르게 끝점도 봐주었다. 끝점(11/30)과 걸치면서 new 시작점이 제일 앞에 있는 구간을 이어주면서 시작했다. 즉, 앞뒤에 구간을 하나씩 이어줄건데,  내가 선택한 구간이 시작점 or 끝점을 포함하고 있는 모든 구간들과 비교했을 때 나쁘지 않은 선택이기 때문이다.

좀 더 설명하면 구간 [c, d) 일 때 d가 11월 30일 보다 뒤에 있는 날짜이면서, 동시에 c의 날짜가 가장 빠른(이른) 구간을 걸어주는 것이다. 그리고 c를 다시 우리가 연결해야 하는 남은 구간의 끝점으로 갱신하면 된다. (여기부터는 이제 이전 구간이 [c, d)  였으므로 c가 포함 된다! 부등호 조심)

 

이런 예시를 볼 때 확실히 2, 4는 절대 손해보지 않는 선택이다.

1, 2는 모두 start에 걸쳐있고 3, 4는 모두 end에 걸쳐있다.  이 그림을 보고 구간 선택을 할 때, 점이 양끝점을 기준으로 더 멀리가면 좋은 이유를 알 수 있다. 지금 구간의 절대적인 길이를 보면 1, 3이 더 길다. 그러나 구간의 절대적인 길이와 상관 없이, 양끝점에 걸치는 조건을 만족하면서 점이 더 멀리가는 2, 4를 택하는게 1, 3과 비교했을 때 절대 손해보지 않는 선택이라는 의미이다.

구간을 앞뒤로 한 번 이어주었을 때 모양새를 비교하면 이렇게 된다. (위 그림을 참고)

3/1 ~ [a, b) 구간      -----(우리가 채워야하는 빈 구간)-----    [c, d) 구간 ~ 11/30(이후에 걸치게)

b가 가능한 가장 늦은 날짜이고, c가 가능한 가장 이른 날짜이면, 우리가 채워야 하는 빈 구간은 최소 길이가 되며, 더 많은 구간을 이을 수 있는 기댓값이 높아진다. (기존에 이어준 구간이 최대로 길어지면서 겹치는 범위가 더 많아질 수 있다.)

그래서 이렇게 반복하면서 구간을 이어주면 된다. 다만, 3/1 ~ 11/30 의 범위를 단 한 번에 포함하거나, 하나씩 걸고 난 후에 [b, c] 범위를 다 포함해버리는 꽃이 존재할 수 있다. 그래서 시작점, 끝점을 완전히 포함하는 구간을 찾으면 cnt +1 해주고 끝내면 된다.

+ 꽃이 1개일 때의 케이스도 조건문으로 처리해주면 된다.

 

---

코드는 최적화고 뭐고.... 일단 자력솔 하느라 일일히 설명을 달아두어서 복잡하다.. 나중에 좀 더 이쁘게 고쳐야지

import sys
from collections import deque

input = sys.stdin.readline
month = [31, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
N = int(input())
f_list = []

# start month/day, end month/day
def solve(t, sm, sd, em, ed, cnt):
    front = []
    end = []
    no = []

    for opt in t:
        if opt[0] < sm or (opt[0] == sm and opt[1] <= sd):
            front.append(opt)
        elif opt[2] > em or (opt[2] == em and opt[3] > ed):
            # 지는 날은 당일이랑 겹치게 하면 안돼
            end.append(opt)
        else:
            no.append(opt)

    # 지금 시간 구성도 sm, sd, em, ed, time 순서
    # 시작일과 겹치는 seg 중에 지는 일이 가장 늦은
    # 종료일과 겹치는 seg 중에 피는 일이 가장 앞선
    # 시작일, 종료일이 모두 겹치면 front, end 둘다 들어감

    front.sort(key=lambda x: (-x[2], -x[3]))
    end.sort(key=lambda x: (x[0], x[1]))

    #print(front, 'front')
    #print(end, 'end')
    #print(no, 'no')

    # front와 end에 0번 인덱스 이후 애들은
    # 무조건 0번과 같거나 그보다 못한 선택임에 유의
    # 남은 seg의 시작일을 front[0]의 끝점,
    # 남은 seg의 끝나는 날을 end[0]의 시작점으로 바꿔서 반복

    if len(front) == 0:
        print(0)  # 잇는게 불가능한 경우
        sys.exit()

    elif len(end) == 0:
        # end 배열이 없고 front[0]로 못끝나면 불가능
        # 왜냐하면 내가 시작점 겹치는걸 front에 먼저 넣어줘서 시작~끝 다 겹치는 구간이 front에 있을 가능성이 있어서 한 번 봐줘야함
        if front[0][2] > em or (front[0][2] == em and front[0][3] > ed):
            print(cnt+1)
        else:
            print(0)
        sys.exit()

    elif front[0][2] > em or (front[0][2] == em and front[0][3] > ed):
        # front, end 배열이 모두 있지만, front에서 한 번에 걸어서 끝나는 경우
        print(cnt + 1)
        sys.exit()

    elif front[0][2] > end[0][0] or (front[0][2] == end[0][0] and front[0][3] >= end[0][1]):
        # 앞, 뒤 하나씩 연결해서 연결이 완성되는 경우
        print(cnt + 2)
        sys.exit()

    else:  # 둘 다 연결했는데 안됐을 때 남은 no 배열으로 다시 돌리기
        sm, sd = front[0][2], front[0][3]
        if end[0][1] == 1:
            em = end[0][0]-1
            ed = month[em]
        else:
            em, ed = end[0][0], end[0][1]-1 #부등호 처리 귀찮아서 그냥 하루 앞으로 돌리기

        if len(no) != 0:
            solve(no, sm, sd, em, ed, cnt + 2)
        else:
            #만약 더이상 연결할 seg가 없으면 불가능
            print(0)
            sys.exit()


if N == 1:  # edge case
    t = list(map(int, input().split()))
    res = True

    if t[0] > 3 or (t[0] == 3 and t[1] > 1):
        res = False
    if t[2] < 11 or (t[2] == 11 and t[3] <= 30):
        res = False
    print(1 if res else 0)

else:
    for _ in range(N):
        t = list(map(int, input().split()))
        f_list.append(t)
    solve(f_list, 3, 1, 11, 30, 0)