[백준] 1931. 회의실 배정

그리디를 사용하는 문제를 파악하기 위해 여러 블로그들을 참고했고, 아래의 블로그에서 풀이방법을 참고했다.

https://velog.io/@contea95/%ED%83%90%EC%9A%95%EB%B2%95%EA%B7%B8%EB%A6%AC%EB%94%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

그리디를 사용할 수 있냐 없냐 하는 것을 직관적으로 알 수 있는 문제도 있지만 어려운 문제를 보면 그리디로 할 수 있을 것 같은데 반례는 없을까? 이게 최적해를 내놓는다는 보장이 있을까? 하는 생각이 들었을 때 이게 그리디 풀이의 해를 보장하는지에 대한 명확한 증명을 하기는 생각보다 까다롭다.

그리디로 풀 수 있는지 어느 정도 알 수 있는 방법을 소개하는 블로그가 있는데, 현재 지식 수준으로는 굉장히 어렵기 때문에 문제도 많이 풀어보고 여러 번 보면서 이해를 해야 할 것 같다.

https://gazelle-and-cs.tistory.com/59

탐욕 알고리즘 분석하기 (Correctness of Greedy Algorithms)

첫번재 링크의 블로그에서 그리디 알고리즘으로 풀 수 있는 문제의 조건으로 2가지를 제시하고 있는데
1. 각 선택이 전체 문제의 최적해를 반드시 도출해야 한다.

2. 최종해결방법이 부분 문제에 대해서도 최적의 해결방법이다.

라는 것이다.

 

그리디의 특징은 전체의 관점에서 최선이 아닌 현재 상태에서 최선을 선택한다는 것이다.

 

<나의 풀이>

n = int(input())
time_list = []
last_idx = 0
cnt = 0
for i in range(n):
    time_list.append(list(map(int, input().split())))
    
time_list.sort(key=lambda x : (x[1], x[0]))

for i in range(len(time_list)):
    if time_list[i][0] >= last_idx:
        last_idx = time_list[i][1]
        cnt += 1

print(cnt)

60196 kb

4300 ms

 

 

<고수님의 풀이 1>

from sys import stdin
def solve():
    n=int(stdin.readline().rstrip())
    dic={}
    trash=0
    ltrash={}
    for i in range(n):
        a,b=map(int,stdin.readline().split())
        if a not in dic and b!=a: dic[a]=b
        elif b==a:
            trash+=1
            if b not in ltrash: ltrash[b]=0
        elif dic[a]>b and b!=a: dic[a]=b 
    for e in ltrash:
        if e not in dic:
            dic[e]=e
            trash-=1
    arr=list(dic)
    arr.sort()
    tmp=dic[arr[0]]
    cnt=1
    for i in range(1,len(arr)):
        if tmp>dic[arr[i]]:
            tmp=dic[arr[i]]
        else:
            if arr[i]>=tmp:
                cnt+=1
                tmp=dic[arr[i]]
    print(cnt+trash)
solve()

43644 kb

184 ms

<고수님의 풀이2>

# 최대 회의 갯수 찾기
# 회의 시작시간이 겹치는 것은 전부 제일 작은걸로 갱신, (제일 작은 값으로 하니까 어떤 경우에 대하여 카운트를 못하는 경우가 발생하여 그냥 저장하는 방식으로 했음)
# 시작시간 키값, 도착시간 밸류로 딕셔너리에 저장할 것임
# 회의 시작 시간 순으로 정렬하여 출력 (keys 만 sort 하여 dic[key] 방식으로 불러올 것임)
# 현재 회의의 종료시간 저장 그리고 종료시간보다 늦은 시작 시간인 녀석이 나오면 종료시간 갱신 및 카운트 더하기 일
# 종료시간보다 종료시간이 더 이른 녀석이 나오면 종료시간 갱신, 카운트는 유지

"""
2번 항목에 대한 반례
3
1 5
2 3
2 2
answer: 2
output: 1
"""

import sys
input = sys.stdin.readline


def solve():
    N = int(input())
    dic = {}
    for _ in range(N):
        start, end = map(int, input().split())
        if dic.get(start):
            dic[start].append(end)  # min(dic.get(start, float('inf')), end)
        else:
            dic[start] = [end]
    
    for k in dic.keys():
        dic[k].sort()
        
    keys = sorted(dic.keys())
    end = 0
    count = 0
    for key in keys:
        for e in dic[key]:
            if e < end:
                end = e
            elif key >= end:
                count += 1
                end = e

    print(count)


solve()

50812 kb

200 ms