[Gold V] 파티가 좋아 파티가 좋아 - 4055

문제 링크

성능 요약

메모리: 31256 KB, 시간: 68 ms

분류

브루트포스 알고리즘, 그리디 알고리즘, 정렬

문제 설명

아람이는 고등학교를 졸업하였다. 아람이네 마을에서는 학교의 모든 졸업생들이 참가할 수 있는 다양한 파티가 관습처럼 열리고 있다. 파티를 좋아하는 아람이는 최대한 많은 파티에 참가하려고 한다.

평일에 열리는 파티는 저녁에만 두세개가 열리지만 토요일에는 하루종일 많은 파티들이 열린다. 어떤 파티는 아침 8시에 시작하여 자정(24시)에 끝나기도 한다. 아람이는 최대한 많은 파티에 참가하고 싶다.

각각의 파티는 시작시간과 끝시간이 정해져있다. 파티는 정각에 시작하여 정각에 끝난다. 예를 들어 10시에 파티가 시작한 파티가 오후2시(14시)에 끝날 수도 있고 가장 일찍 시작하는 파티는 아침 8시에 시작하고 이웃들의 항의가 있을 수 있기 때문에 아무리 늦게 끝나도 24시에는 끝나게 된다. 파티에 있을 때는 최소한 30분은 있어야 예의에 어긋나지 않는다. 아람이는 예의를 지키는 사람이다. 아람이는 축지법을 쓰기 때문에 파티간 이동시간은 신경쓰지 않아도 된다. 더 이상 참가할 파티가 없으면 아람이는 집에 돌아간다.

아람이가 갈 수 있는 최대 파티 수는 몇 개인지 찾는 프로그램을 작성하시오.

입력

여러 개의 테스트케이스가 주어진다 각 테스트케이스는 첫 번째 줄에 정수 p가 주어진다. (p ≤ 100) 이 p는 파티의 그 날에 열리는 파티의 수이다. p가 0이면 입력의 끝을 의미한다. 이어지는 p개의 줄에는 s와 e가 주어진다. (8 ≤ s < e ≤ 24) s는 파티의 시작시간을 의미하고 e는 파티가 끝나는 시간을 의미한다. 시작시간과 끝시간이 같은 파티가 주어질 수도 있다.

출력

다음의 출력 형식에 맞추어 출력하시오.

On day d Emma can attend as many as n parties.

n은 최대 갈 수 있는 파티의 수이고 d는 몇 번째 테스트 케이스인지를 가리킨다. 테스트케이스는 1부터 시작한다.

---

풀이

아이디어

처음 생각한 아이디어는 각 시간에 대해 진행되는 파티의 가중치를 두고 (더 긴 파티의 경우 이른 시간에 더 큰 가중치를 두어 선택을 유보하는 방식이다.) 개수를 세어나가는 방식이었다.
그림으로 나타내면 다음과 같을 수 있다.

# 파티 시간표만 표시

8 9
8 9
8 12

파티에 참가한다 라는 조건은 최소 30분은 있어야 한다는 조건이며, 문제 자체에서 30분 단위로 끊지 않기 때문에 1시간을 하나의 파티라고 생각하고 한 행을 파트로 구분하였다.

그렇기 때문에 모든 파티는 총 24개 파트로 구분이되며, 사용되는 파트는 16개 파트가 된다.
가중치를 두는 코드는 아래와같이 구현하였다

    for p in party:
        tmp = 0
        for i in range(p[1], p[0] - 1, -1):
            if tmp:
                timetable[i].append(tmp)
            tmp += 1

30분씩 참가가 가능하므로 한 파트에서 참가 가능한 파티는 최대 2개가 된다. 이를 기준으로 파티를 선택한다.

    res = 0
    for p in timetable:
        mx = 2
        while mx:
            if p != []:
                p = sorted(p,reverse=True)
                res += 1
                p.pop()
            mx -= 1
    print(print_result(day, res))

첫번째 조건에서 구현한 전체 코드는 다음과 같다.

def print_result(d,n):
    return f"On day {d} Emma can attend as many as {n} parties."

def solve(cnt, day):
    party = sorted([list(map(int, input().split())) for _ in range(cnt)], key=lambda x:x[0])
    timetable = [[] for _ in range(25)]
    
    for p in party:
        tmp = 0
        for i in range(p[1], p[0] - 1, -1):
            if tmp:
                timetable[i].append(tmp)
            tmp += 1
    
    res = 0
    for p in timetable:
        mx = 2
        while mx:
            if p != []:
                p = sorted(p,reverse=True)
                res += 1
                p.pop()
            mx -= 1
    print(print_result(day, res))

if __name__ == "__main__":
    cnt = int(input())
    day = 0
    while cnt:
        solve(cnt, day+1)
        cnt = int(input())
        day += 1

이 코드에서 빼먹은 부분이 있는데 이미 참가한 파티의 경우 삭제를 해주어야 한다.
따라서 다음과 같은 테스트 케이스가 들어오면 틀리게 된다.

#input
5
12 13
12 13
12 13
12 15
12 15
0

#result
On day 1 Emma can attend as many as 6 parties.

#answer
On day 1 Emma can attend as many as 4 parties.

이 매커니즘대로라면 삭제하는데 자료구조부터 다시 설계해야한다 따라서 다른 답을 참고하였다.
이 코드는 다음과 같이 동작한다.

1. 문제 상의 한계를 먼저 정의한다. 최대 파티의 수를 100개로 정의했는데, 문제상에서 최대 파티의 수는 100개이기 떄문이다.
2. 시작시간과 끝나는 시간을 담은 리스트 자료구조를 생성한다. 파티는 8시에 시작하여 24시에 종료되며, 입력된 순서대로 리스트 인덱스에 저장된다.
   여기서 인덱스에 저장하는 방식이 중요한데 8시부터 시작하므로 편리를 위해 -8을하여 기준을 0으로 맞추어 주었고, 1시간에 2개의 파티를 참가할 수 있으므로 2를 곱해주어 간격을 조정하였다.

start[i] = (s-8)*2
end[i] = (e-8)*2

3. 참가 가능한 파티의 수를 세는 부분인데, best_index에서 인덱스의 값이 양수인 경우 수를 늘려주며, 시작 시간을 한계치로 바꿔주어 제거한다. 여기서 start[index] = 32가 그 역할인데 이미 선택한 파티 인덱스의 경우 제거하여 더이상 선택에 포함되지 않게 하는 역할이다.
   왜 32로 초기화 해주냐면 바뀐 인덱스에서 한계값이 32이기 때문이다. (24-8)*2

4. best_index 함수는 입력된 파티의 시간을 모두 순회 탐색하는데 완전 탐색을 하되, t가 1부터 32까지 순증가 하므로 완전탐색을 한다.
   또한 가장 빠른 파티부터 선택할 수 있다.

전체 코드는 아래와 같다.

코드

MAX_PARTY = 100
start, end = [0]*MAX_PARTY, [0]*MAX_PARTY

def print_result(d,c):
    print(f"On day {d} Emma can attend as many as {c} parties.")


def best_index(t, np):
    index = -1
    earliest = 33

    for i in range(np):
        if start[i] <= t < end[i] and end[i] < earliest:
            index = i
            earliest = end[i]
    return index


p = int(input())
day = 0
while p:
    day += 1
    for i in range(p):
        s, e = map(int, input().split())
        start[i] = (s-8)*2
        end[i] = (e-8)*2
    
    count = 0
    for i in range(32):
        index = best_index(i, p)
        if index >= 0:
            count += 1
            start[index] = 32

    print_result(day, count)
    p = int(input())

---

회고

ICPC 문제였고, CPP로 작성된 정답 코드를 파이썬으로 옮긴것이다. 정확한 매커니즘 파악에 오래걸렸는데 내가 이런 코드를 짤 수 있을까 걱정이 됐다.. 이게 GV 수준이라니..