[백준 / BOJ] 13907 세금

문제

출처 : https://www.acmicpc.net/problem/13907

13907번: 세금

주언이는 두 도시를 오가며 무역을 한다. 이때, 도시의 통행료가 가장적은 길로 이동을 하려고한다. 도시들은 양방향으로 연결되어있으며 도로마다 통행료가 존재한다.

나라에서 도로의 통행료를 인상시킬려고한다. 통행료를 A만큼 인상시켰다면, 모든 도로의 통행료는 A만큼 증가한다.

 

주언이의 최초 최소통행료와, 세금이 오를때마다의 최소 통행료를 구하는 문제다.

 

풀이

다익스트라와 그리디로 풀은문제다.

 

다익스트라만 사용하여 세금이 오를때마다 최솟값을 구한다 해보자.

매번 최소 경로를 찾는 반복값은 Mlog(N) = (최대 90000)이며, 쿼리가 30000주어지므로, 총 반복값은 2700000000이 되어서 시간안에 통과하지못한다.

따라서, 다익스트라에 트릭???을 적용해서 문제를 풀어야했다.

 

A. 우선, 세금이 오를때마다 최솟값을 구하는 과정에 걸리는 시간을 다음 방법으로 최소화 할수있다.

- 도착도시에 도착한 최솟값을 지나온도시의 수와 함께 저장한다.

ex) check[지나온 도시의 수][도착도시] = 최솟값

이렇게 저장하는 이유는, 다음과 같다.

-> 도착도시 D에 도착하는 경로가 총 2가지 있다고 가정하자.

 

1. 100개의 경로를 지나쳐 도착도시 D에 도착했으며 이때 최솟값은 100임

2. 2개의 경로를 지나쳐 도착도시 D에 도착했으며 이때 최솟값은 200임

 

어떤 세금 인상도 없을때, 답은 당연히 1번 경로이다. 하지만, 나라에서 세금인상을 5만큼 했을경우, 위의 경로의 최솟값은 다음과 같이 변한다.

 

1. 100개의 경로를 지나쳐 도착도시 D에 도착했으며, 이때 최솟값은 100 + 100*5(100개의 경로를 지나쳤으므로..) 임

2. 위와 마찬가지로 200 + 2*5임

 

이때, 답은 2번 경로이다. 따라서, 도착도시에 도착한 최솟값과 이때지나온 도시의수를 같이 저장해주면, O(1)만에 값을 업데이트 해줄수있다.

 

B. 그 다음은 도착도시에 도착하는 모든 경로중, 최솟값을 갖는 경로를 찾는과정을 최적화했다.

A번에서 구한 도착도시에 도착했을때, 값을 {도착도시에 도착했을때의 최솟값, 지나온 도시의 수}와 같이 저장해주자.

이때, 지나온 도시의 수는 N의 값과 같으므로 최대 1000까지 증가한다.

 

봐줄필요 없는경우를 줄이며 최적화 시켜줄수있는데,

우선, 최솟값기준으로 정렬을 해준다. 그후 앞에서 부터 순차적으로 탐색하며, 어떤경로가 다른 경로에대해, 도착도시에 도착했을때의 최솟값, 지나온 도시의 수 모두 크다면, 해당 경로는 절대 최소경로가 될수없다. 이런 경로들을 제거해주며 최적화 시켜주면 된다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/13907%20%EC%84%B8%EA%B8%88/main.cpp

devxb/JJUNalgo