S1 1931. 회의실 배정

문제 보기 :  1931번: 회의실 배정 (acmicpc.net)

---

문제

• 정답률 : 30%

---

작성 코드 & 풀이 과정 코멘트

## 그리디 알고리즘

T = int(input())
graph = [list(map(int,input().split())) for _ in range(T)]
p = max(max(graph))
graph.sort(key=lambda x:(x[1],x[0])) #끝나는 시간 순으로 정렬

now = 0
count = 0

for start, end in graph:
    if start >= now :
        now = end #그 회의 끝난 시간
        count += 1

print(count)

 

처음에는 DFS로 풀이했다.. {1: [4], 3: [5, 8], 0: [6], 5: [7, 9], 6: [10], 8: [11, 12], 2: [13], 12: [14]} 이렇게 두고 한 경로씩 찾아서 가장 많이 갈 수 있는 걸 찾아야하는줄 알았지 모야..

근데 문제를 잘 안 읽어서....; 몹쓸 버릇 때문에 시간 낭비를 했다. 꼭 종료 시간과 새 시작 시간이 연결될 필요가 없다는 부분을 간과해서 저렇게 뻘짓을 한 것...

그래서 두번째 시도엔 bfs로 풀이하려 했지만, 전체 케이스가 10만개라서 시간초과가 발생했고 아.. 그리디 탐색이구나..ㅎㅎ를 했다.

그리고 고군분투했던 거에 비해 너무 간단하게 해결.. (코쓱)