https://www.acmicpc.net/problem/3090
3090번: 차이를 최소로
각각의 테스트 케이스에 대해서, 점수는 (100×(S+1)/(D+1))/(데이터 개수) 점이다. 이때, D는 출력한 수열에서 인접한 수의 차이의 최댓값, S는 정답이다. 즉, 출력한 수열이 정답인 경우 10점을 얻게
www.acmicpc.net
재밌는 파라메트릭 문제다.
k를 매개변수로 잡고 차이가 k보다 작거나 같도록 만들 수 있는지에 대해 파라메트릭 서치를 하면 된다.
그러면 k가 주어졌을 때 그 여부를 알아내는 알고리즘을 작성해야 하는데, 이는 다익스트라에서 아이디어를 구했다. 전부 우선순위 큐에 때려박고, 작은 지점부터 보면서 양쪽에 k보다 차이가 큰 지점이 있으면 그 지점을 낮춰 주고 Update하고 큐에 넣으면 된다. 각 과정에서 사용된 연산의 수를 합해서 T와 비교하면 된다. 이렇게 하면 다익스트라와 비슷한 방식으로 낮추는 과정에서 문제가 생기지 않는다.
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 9376 탈옥 (0) | 2023.01.24 |
|---|---|
| 백준 3653 영화 수집 (0) | 2023.01.23 |
| 백준 7469 K번째 수 (0) | 2023.01.05 |
| 백준 15972 물탱크 (0) | 2023.01.05 |
| 백준 22348 헬기 착륙장 (0) | 2023.01.05 |
