글 읽기 - ★☆★☆★ [필독] ACM Craft FAQ ★☆★☆★

djm03178 5년 전 34

먼저 지어야 하는 건물부터 규칙이 주어진다는 보장이 없습니다. 예를 들어 1->2, 2->3이라는 규칙이 있다면 꼭 1 2 다음에 2 3이 주어지는 것이 아니라 반대로 2 3이 먼저 주어지고 1 2가 다음에 주어질 수도 있습니다. 그러니까 모든 규칙을 입력받기 전까지는 무엇을 먼저 해야 하는지 알 수 없고, 규칙을 입력받으면서 문제를 해결해나갈 수는 없습니다. 모든 규칙을 입력받은 뒤에 계산을 시작해야 합니다.
1번 건물을 가장 먼저 지어야 한다는 보장도 없습니다. 건물의 번호는 그저 번호일 뿐이고 순서와는 아무런 상관이 없습니다. 1번 건물을 마지막으로 지어야 할 수도 있고, 중간에 지어야 할 수도 있으며, 가장 먼저 지을 수 있는 건물이 여럿일 수도 있습니다.
이 문제는 BFS나 다익스트라 등으로는 풀 수 없습니다.
1. BFS: 처음 지어야 하는 건물들부터 시작해서 어떤 건물을 짓기까지 거쳐야 하는 규칙의 수가 다 다를 수 있습니다. 그 규칙을 모두 거치기 전까지는 그 이후의 건물들에 대한 계산을 해서는 안 됩니다. 그렇기 때문에 단순히 규칙 하나씩 나아가는 것은 불가능합니다. 단, 어떤 건물을 짓기 위한 규칙이 모두 계산된 뒤에 큐에 넣어서 계산하는 것은 가능하고, 유효한 풀이 방법 중 하나입니다.
2. 다익스트라: https://www.acmicpc.net/board/...
DFS로 완전 탐색을 해서도 안 됩니다. 한 번 방문한 건물에 대해 재계산을 하는 것이 길게 이어지면 지수 복잡도의 풀이가 되고 이는 절대로 통과될 수 없습니다. 메모이제이션을 이용한 DP를 해야 합니다. https://www.acmicpc.net/board/...
재귀 DP의 경우 초기값은 DP의 결과로 나올 수 없는 값이어야 합니다(또는 방문 체크를 따로 해야 합니다). 예를 들어 이 문제에서 DP의 초기값으로 사용해서는 안 되는 값 중 하나는 0입니다. 건물을 짓는 데에 걸리는 시간이 0일 수 있기 때문에 DP의 결과값으로 0도 역시 유효합니다. 이런 경우에 유효한 값임을 인지하지 못하고 재탐색을 한다면 최악의 경우 지수 형태의 시간복잡도가 나오게 되고 4번과 같은 이유로 시간 초과를 받게 됩니다. ~~네, 제가 전에 이 데이터를 추가했습니다.~~
테스트케이스마다 초기화를 잘 하세요. 이전 케이스에서 사용한 간선 정보 등이 남아있어서는 안 됩니다. 또한 테스트케이스마다 개행 문자를 반드시 출력하세요.
혹시 문제 풀이를 시작한지 얼마 되지 않았고 문제 번호 순으로 푸는 것을 도전 중이시라면, 그 전략은 이 문제를 마지막으로 접어두시는 걸 추천합니다. 다음 문제가 매우 매우 어렵고 이후에는 더더욱 끔찍한 난이도의 문제들이 널렸습니다.

jung2381187 5년 전 7

막줄이 핵심

kyo20111 5년 전 1

팬이에요

bhj2849 4년 전 0

감사합니다. :)

jangzzang 4년 전 0

문제 난이도에 비해서 정답률도 너무 낮고, 질문글도 많길래 이유를 찾아보고 있는데, 번호 순서대로 푸는 분들이 많나 보군요..

댓글을 작성하려면 로그인해야 합니다.