백준 1931번 회의실 배정

 

dp같은 방식으로 풀어봤다.

import sys
n=int(sys.stdin.readline().rstrip())
graph=[]
for _ in range(n):
    graph.append(list(map(int,sys.stdin.readline().rstrip().split())))
graph.sort(key=lambda x:x[1])
v=[0]*(graph[-1][1]+1)
for i in range(len(graph)):
    v[graph[i][1]]=max(v[graph[i][0]]+1,v[graph[i][1]-1])
result=0
for i in range(len(v)):
    result=max(result,v[i])
print(result)

 

기본적으로 입력받은 간선은 가중치1짜리라고 생각하고 나머지 모든 정점에 가중치 0짜리 간선이 들어갔다고 생각하자

 

이렇게 생각하고 구현하려 했는데 도저히 방법을 모르겠어서 그냥 풀이를 봤다.

 

그냥 끝나는 시간과 시작시간을 기준으로 정렬해준다음 시작시간이 이전 끝나는 시간보다 빠르면 count를 늘려준다.

진짜 충격적인 풀이였다.

 

 

import sys
n=int(sys.stdin.readline().rstrip())
graph=[]
for _ in range(n):
    graph.append(list(map(int,sys.stdin.readline().rstrip().split())))
graph.sort(key=lambda x:(x[1],x[0]))
count=1
v=graph[0][1]
for i in range(1,n):
    if graph[i][0]>=v:
        count+=1
        v=graph[i][1]
print(count)