1766. 문제집

이거 하나 푸느라 4일동안 다른 생각을 못 했다. 지금의 나는 이 정도인 것 같다. ㅠㅠ

1766번: 문제집

---

가장 쉬운 문제부터 가장 어려운 문제까지 푸는데, '먼저 풀면 좋은 문제'를 고려해야 한다.

제일 먼저 떠오른 해결책은 dfs였다. 1번 문제부터 차례대로 '먼저 풀면 좋은 문제'를 난이도 순으로 모두 푼 다음 본 문제를 풀면 되지 않겠는가? 

 

그러나 이것이 맞았더라면 내가 이 글을 쓸 이유도 없었다. ㅋㅋ

위의 논리의 허점은 문제를 greedy로 접근했다는 것이다. 게시판에 있는 다음 예제를 살펴보자.

5 4
4 1
5 1
2 5
3 5

나의 생각대로 문제를 풀어 보자.

우선 1번 문제를 풀어야 한다. 1번 문제를 풀기 위해 4, 5번 문제를 먼저 풀어야 한다. 4번 문제는 바로 풀 수 있으므로 먼저 풀고, 5번 문제를 풀자. 그런데 5번 문제를 풀려면 2, 3번 문제를 풀어야 한다. 두 문제 모두 바로 풀 수 있으므로 순서대로 2, 3번 문제를 풀고, 5번 문제를 푼다. 이제 1번 문제를 푼다. 따라서 정답은 다음과 같다.

4 2 3 5 1

물론 이것은 틀린 답이다. 어째서 그러한지 그래프를 보면서 분석해 보자.

1번 문제를 풀기 위해 4, 5번 문제를 풀어야 하는 것은 맞다. 하지만 4번 문제를 먼저 푼 것은 잘못되었다. 2, 3번 문제를 먼저 풀 수 있기 때문이다. 따라서 정답은 다음과 같다.

2 3 4 5 1

(적어도 내 생각에는) dfs로는 이 문제를 해결할 수 없다.

할 수 없이 새로운 방법을 찾아야만 했다.

---

위상 정렬은 그래프에서 해야 하는 일의 "순서"를 찾는 알고리즘이다. 이 문제에 딱 맞는 알고리즘이다..만 사실 떠올리지 못했다.

 

입력으로부터 그래프를 만들고, 위상 정렬을 수행하면 된다. 여기서 위상 정렬의 구현을 소개하지는 않겠다.

---

언젠가 이런 문제를 뚝딱 풀어버리는 날이 올까?