[BOJ 24888] 백준 24888번 - 노트 조각
| 2022 숭고한 연합 알고리즘 콘테스트 Open Contest 풀이 | ||
|---|---|---|
| A | [BOJ 24883] 자동완성 | |
| B | [BOJ 24884] 장작 넣기 | |
| C | [BOJ 24885] 주식 | |
| D | [BOJ 24886] SKH 문자열 | |
| E | [BOJ 24887] 최대한의 휴식 | |
| F | [BOJ 24888] 노트 조각 | |
| I | [BOJ 24891] 단어 마방진 |
1. 문제
$24888$. 노트 조각 (2022 숭고한 연합 알고리즘 콘테스트 F번)
2. 풀이
lobo_prix와jhnah917의 출발지는 $1$번 정점, 도착지는 $N$번 정점으로 동일하다.- 둘의 이동속도는 동일하며, 오직 간선의 길이만 가중치로 적용된다.
jhnah917는 최단 경로로만 이동한다.- 가장 먼저 도착한 사람이 우승이며, 여러 명이 동시에 도착하면 그 여러 명 전부 우승이다.
위의 문제의 조건을 토대로 lobo_prix가 우승하려면, jhnah917처럼 어떠한 최단 경로로 이동하여 jhnah917와 동시에 도착하는 방법밖에 없다. 따라서 모든 최단 경로를 찾고, 그 최단 경로 중에서 모든 노트 조각을 줍는 경우를 찾으면 된다.
한 곳에서 다른 곳으로 가는 최단 경로를 구하는 문제이므로, Dijkstra(다익스트라)알고리즘을 사용한다.
먼저, Dijkstra를 돌려 $1$(시작점)에서 모든 곳으로의 $Dist$(최단거리)를 구한다. 이때, 최단거리를 갱신할 때마다 $A$의 합도 같이 갱신해준다.
$A$의 합은 전체 노트의 합이 되어야 하므로 최대한 커야 한다. 따라서 중복 값은 maximum으로 갱신해준다. 또한, 최단 경로가 여러 개여도 전부 탐색 가능해야 하므로, Dist[next] == ncost일 때도 $A$의 합을 갱신해준다.
A_cnt[N]이 전체 노트의 합이 아닐 경우, 노트 조각을 전부 줍지 못하므로 -1을 출력한다.
이제 다익스트라를 통해 만든 Dist 배열과 A_cnt 배열의 정보를 바탕으로, 도착지 $N$에서 시작점 $1$로 거슬러 올라가면 된다.
노트 조각을 전부 줍지 못하는 경우는 이미 예외처리 되었고, 최단 경로이면서 노트 조각을 주웠던 상황을 바탕으로 거슬러 올라간다. 따라서, 다시 이전 재귀로 되돌아가는 상황 없이 한번에 목적지에 도달할 수 있다.
3. 채점 결과
4. 회고
처음에 자료형을 한 곳에서 잘못 설정해서 WA를 받았고, for문에서 M을 써야 하는데 N을 써서 WA를 받았다. 사소한 실수를 줄일 수 있도록 좀더 신경써야겠다.
원래 구현한 방법이 재채점 후에 시간초과를 받아서, 2022/05/10일 코드를 수정하여 다시 성공하였다. 노드별 노트합을 미리 구해서 백트래킹을 한 줄기로 바로 끝 노드를 향하게 만드는 것이 핵심이었다.
댓글남기기