Joonas' Note

BOJ 1766 - 문제집 본문

알고리즘/문제 풀이

BOJ 1766 - 문제집

joonas 2018.05.22 16:51

[이전 블로그]에서 글 옮김

링크: https://www.acmicpc.net/problem/1766

풀이

처음에는 문제의 접근 방향을 후위순회처럼 생각했다. 어떤 x번째를 하기 위해서 그 이전것을 무조건 해결해야하는 방식.
틀리고 나서 문제를 다시 이해했는데, 깨달은 테스트 케이스부터 말하자면 아래와 같다.

5 3
4 1
2 3
5 3

내가 생각한 이 입력의 정답은 아래와 같다.

2 4 1 5 3

1번보다 4번을 먼저 풀어야하고, 3번보다 2, 5번을 먼저 풀어야한다. 1번을 풀기 위해서 4번을 풀어야하는데, 같은 우선순위에서 4번보다는 2번이 쉽다.
(둘 다 1개의 문제 앞에 있음)2번을 풀고 4번을 풀면, 1번이 풀리고 남은 5번을 풀면 3번이 풀린다.

처음에 생각한 대로라면 4 1 2 5 3 이 나와야하는데, 이게 틀려서 위 생각으로 다시 풀었더니 맞았다.

위상정렬 도중에 indegree가 없는 정점을 선택할때마다 번호가 작은(문제 난이도가 낮은) 정점을 선택하게 하면 된다.

코드

코드보기

'알고리즘 > 문제 풀이' 카테고리의 다른 글

BOJ 1509 - 팰린드롬 분할  (0) 2018.07.18
BOJ 3079 - 입국심사  (0) 2018.05.25
BOJ 1766 - 문제집  (0) 2018.05.22
BOJ 13701 - 중복 제거  (0) 2018.05.18
BOJ 15719 - 중복된 숫자  (0) 2018.05.18
BOJ 15683 - 감시  (0) 2018.05.17
0 Comments
댓글쓰기 폼