[문제 보러 가기]
처음 이 문제를 접했을 때는 기나긴 영문 문제의 압박으로 인해서 처음엔 손을 대고 싶지 않은 문제 중 하나가 아니었을까 싶습니다.
이 문제가 요구하는 바를 다음 두 가지 부분문제로 나타낼 수 있습니다.
각 client 에 서비스를 제공할 때 각각 소요되는 비용 구하기
이 비용을 가지고 budget 내에서 서비스를 제공했을 때 최대의 priority 구하기
이 두가지 부분 문제를 각각 개별적으로 해결해 봅시다.
1. 각 client 에 서비스를 제공할 때 각각 소요되는 비용 구하기
우선 서비스 비용은 문제에 주어져 있듯 (client에게 주어져 있는 cost) * (facility에서 client까지 가는데
드는 거리 비용) 으로 구할 수 있습다. 여기서 client에게 주어져 있는 cost 의 경우엔 입력에서 주어진 고정값이므로
서비스 비용은 facility 에서 client 까지 드는 거리 비용만 알고 있으면 쉽게 구할 수 있습니다. 따라서 첫번째
문제는 시작점(facility가 위치한 정점) 으로부터 모든 정점까지의 최단경로를 구하는 문제로 바뀌게 됩니다. 이와 같은
문제를 Single-source shortest path problem 이라고 하는데, 잘 알려져 있는 Dijkstra's shortest path algorithm 이나 Bellman-Ford shortest path 알고리즘을 이용해 풀 수 있습니다. 하지만 저의 경우엔 Floyd-Warshall
의 모든 쌍에 대한 최단 경로 알고리즘을 사용 하였습니다. O(N^3) 의 시간 복잡도를 가지고 있어서 N = 100 인 이
문제에서는 빠른 시간 내에 돌아가고, 구현이 간단하여 코딩 실수를 줄일 수 있기 때문에 이 알고리즘을 선택한 것입니다.
(알고리즘의 구현은 아래 소스 코드의 floyd()를 참고하길 바랍니다.)
2. 이 비용을 가지고 budget 내에서 서비스를 제공했을 때 최대의 priority 구하기
최단 경로를 구한 다음 서비스 비용을 계산 해주고, 이를 통해서 priority의 값을 budget내에서 최대화 시키는 문제를
풀게 됩니다. 주어진 값 내의 조합의 최대 값과, 해당 client에게는 한번의 서비스만 가능하다는 점을 보면, 사실이 문제는 0/1 배낭 채우기 문제 라는 유명한 문제와 같다는 것을 알 수 있습니다. 이 문제는 Brute-force 한 방법을 통해서 풀기에는 최악의 경우 O(2^100)의 시간 복잡도를 가지게 됩니다. 허나 budget의 숫자가 100이하 이므로 pseudo-polynomial 한 동적 계획법(Dynamic Programming) 을 통해서 문제를 풀 수 있으며, 점화식은 다음과 같습니다.
D[i][j] = max( D[i-1][j], D[i-1][j-cost[i]] + priority[i] );
= i번 클라이언트까지 고려했고, 지금까지 j만큼의 budget을 사용 하였을 때의 최대값
여기서 cost[i]는 i번 client에게 서비스 할때 소요되는 비용, priority[i]는 i번 client의 proirity를 의미 합니다. 점화식을 통해 답은 D[N][budget]에 저장되게 됩니다.
이 해법 역시 상태의 개수가 2개 이기 때문에 선뜻 봤을 때는 2차원 배열을 잡아서 풀어야 할 거라고 생각되지만, D[i][j] 를 계산하기 위해 필요한 값은 D[i-1] 에 들어 있는 값들밖에 없기 때문에 E번에서 그러 하였듯, F번에서도 하나의 배열로 해를 구할 수 있습니다.(자세한 구현은 아래 소스 코드의 solve()를 참고 하기를 바랍니다.)
PS. 이 문제를 풀 때, 임의의 client와 facility의 경로가 존재 하지 않을 경우가 입력에 있을 수 있으므로, 이 부분에 대해서 유의해 코딩을 해야 합니다. (실제로 저의 경우에 이 경우를 제대로 처리 해주지 않아서 2번의 runtime-error를 받았습니다:()
admin
[문제 보러 가기]
처음 이 문제를 접했을 때는 기나긴 영문 문제의 압박으로 인해서 처음엔 손을 대고 싶지 않은 문제 중 하나가 아니었을까 싶습니다.
이 문제가 요구하는 바를 다음 두 가지 부분문제로 나타낼 수 있습니다.
1. 각 client 에 서비스를 제공할 때 각각 소요되는 비용 구하기
우선 서비스 비용은 문제에 주어져 있듯 (client에게 주어져 있는 cost) * (facility에서 client까지 가는데
여기서 cost[i]는 i번 client에게 서비스 할때 소요되는 비용, priority[i]는 i번 client의 proirity를 의미 합니다. 점화식을 통해 답은 D[N][budget]에 저장되게 됩니다.드는 거리 비용) 으로 구할 수 있습다. 여기서 client에게 주어져 있는 cost 의 경우엔 입력에서 주어진 고정값이므로
서비스 비용은 facility 에서 client 까지 드는 거리 비용만 알고 있으면 쉽게 구할 수 있습니다. 따라서 첫번째
문제는 시작점(facility가 위치한 정점) 으로부터 모든 정점까지의 최단경로를 구하는 문제로 바뀌게 됩니다. 이와 같은
문제를 Single-source shortest path problem 이라고 하는데, 잘 알려져 있는 Dijkstra's shortest path algorithm 이나 Bellman-Ford shortest path 알고리즘을 이용해 풀 수 있습니다. 하지만 저의 경우엔 Floyd-Warshall
의 모든 쌍에 대한 최단 경로 알고리즘을 사용 하였습니다. O(N^3) 의 시간 복잡도를 가지고 있어서 N = 100 인 이
문제에서는 빠른 시간 내에 돌아가고, 구현이 간단하여 코딩 실수를 줄일 수 있기 때문에 이 알고리즘을 선택한 것입니다.
(알고리즘의 구현은 아래 소스 코드의 floyd()를 참고하길 바랍니다.)
2. 이 비용을 가지고 budget 내에서 서비스를 제공했을 때 최대의 priority 구하기
최단 경로를 구한 다음 서비스 비용을 계산 해주고, 이를 통해서 priority의 값을 budget내에서 최대화 시키는 문제를
풀게 됩니다. 주어진 값 내의 조합의 최대 값과, 해당 client에게는 한번의 서비스만 가능하다는 점을 보면, 사실이 문제는 0/1 배낭 채우기 문제 라는 유명한 문제와 같다는 것을 알 수 있습니다. 이 문제는 Brute-force 한 방법을 통해서 풀기에는 최악의 경우 O(2^100)의 시간 복잡도를 가지게 됩니다. 허나 budget의 숫자가 100이하 이므로 pseudo-polynomial 한 동적 계획법(Dynamic Programming) 을 통해서 문제를 풀 수 있으며, 점화식은 다음과 같습니다.
이 해법 역시 상태의 개수가 2개 이기 때문에 선뜻 봤을 때는 2차원 배열을 잡아서 풀어야 할 거라고 생각되지만, D[i][j] 를 계산하기 위해 필요한 값은 D[i-1] 에 들어 있는 값들밖에 없기 때문에 E번에서 그러 하였듯, F번에서도 하나의 배열로 해를 구할 수 있습니다.(자세한 구현은 아래 소스 코드의 solve()를 참고 하기를 바랍니다.)
PS. 이 문제를 풀 때, 임의의 client와 facility의 경로가 존재 하지 않을 경우가 입력에 있을 수 있으므로, 이 부분에 대해서 유의해 코딩을 해야 합니다. (실제로 저의 경우에 이 경우를 제대로 처리 해주지 않아서 2번의 runtime-error를 받았습니다:()
16년 전