주간 문제풀이 07 (BOJ 5551 / 14458 / 5896)

이번주는 앞 3문제만 풀었다. 나머지 두 문제는 어려웠다.

 

BOJ 5551 - 쇼핑몰 (P5)

https://www.acmicpc.net/problem/5551

문제: 무향 가중치 그래프가 주어지고, N개의 노드 중 K개는 쇼핑몰이다. 쇼핑몰에서 최단경로로 가장 멀리 떨어진 지점을 구하는데, 이때 지점은 노드뿐만이 아니라 간선 위의 어느 한 점이 될 수도 있다. 가장 멀리 떨어져 있는 지점이 얼마나 멀리 있는지 구하면 된다.
풀이:

일단 그냥 평범하게 노드까지의 최단경로를 구한다. 그 후에, 각 간선을 보면서 간선 위에서 가장 거리가 먼 지점은 어디인지를 따로 구해주면 된다.

 

예를 들어서 (u, v)를 연결하는 가중치 w의 간선이 있는데,  dist[u] = 10, dist[v] = 13, w = 4라면, 이 간선 위에서의 가장 먼 지점은 거리가 13.5가 된다. (u에서 출발하고 3초 뒤에 v에서 출발했을 때, 간선 위의 어디에서 만나게 되는지 상상해 보자) 즉 (dist[u] + dist[v] + w) / 2 로 간선 위에서의 가장 먼 지점을 구할 수 있다.

 

코드: https://www.acmicpc.net/source/share/5216d58013d14352ba6e53f1f917a953

 

BOJ 14458 - 소가 길을 건너간 이유 10 (P4)

https://www.acmicpc.net/problem/14458

14458번: 소가 길을 건너간 이유 10

문제: 일자형 길 양쪽에 목초지가 각각 N개 있다. i번 목초지는 왼쪽과 오른쪽에 각각 한개씩 있고, i번 목초지 두 개를 이어줄려고 한다. 이 때 목초지 a의 경로와 b의 경로가 겹칠 수 있는데, 그러면 (a, b)를 가로지르는 쌍이라고 부른다. 가로지르는 쌍을 최소화하도록 왼쪽이나 오른쪽 중 한 쪽의 목초지를 회전할 때, 가로지르는 쌍의 최소 개수를 구하라.

풀이:

배열 P를 "P_i = A_i 의 B 배열에서의 위치" 로 정의해보자. 가령 이런 식이다.

"가로지르는 쌍"의 개수는 P에서의 inversion개수와 같다. (inversion과 가로지르는 쌍 모두 P에서 뒤에 있는 수의 P_i값이 더 작을 때 발생한다)

먼저 초기에 주어진 배열의 inversion을 세야 한다. 이건 세그트리나 펜윅트리를 활용한 방법도 있고, order statistics tree를 활용하는 방법도 있다.(코드에서는 order statistics tree를 사용했다.)

그 후에는 A나 B 배열을 회전할 때 inversion개수가 어떻게 변하는지 확인해야 하는데, 이때 B배열을 회전한다고 생각하면 P는 가장 작은 수를 제외하고 모든 수가 1 줄어들고, 가장 작은 수가 가장 큰 수로 변하게 된다. 가령 첫 사진에서의 B배열을 한 칸 회전시키면 P배열은 아래와 같이 변한다.

-1 된 수들 사이에서는 inversion은 변하지 않고, 가장 작은 수에서 가장 큰 수로 변한 위치 하나에 대해서만 inversion 개수 변화를 추적하면 된다. 좀 더 정확히는, 원래 가장 작은 수 앞에 있던 수 개수 만큼 inversion이 빠지고, 그 수 뒤에 있는 수 개수만큼 inversion이 추가된다. 이렇게 회전을 한 칸씩 하면서 가장 적은 inversion개수를 구할 수 있다. 여기까지 NlogN에 풀 수 있다.

A를 회전시킬 때와 B를 회전시킬 때의 답은 다를 수 있다. (직관적으로만 이해하자면: 같은 숫자가 만나는 위치가 두 가지 경우에 대해서 다르다) 즉 두 가지 경우 다 해봐야 한다.

코드: http://boj.kr/bccd572ce55e4088a6815e9525add724

 

BOJ 5896 - 효율적으로 소 사기 (P3)

문제: 살 수 있는 소 N마리가 있고, 각 소는 쿠폰을 썼을 때 P원, 쓰지 않았을 때 C원이다. M원과 K개의 쿠폰이 있을 때, 최대 몇 마리의 소를 살 수 있는지 구하자.

풀이:

먼저 쿠폰을 쓸 때 가장 싼 소 K마리를 가져오고, 그 후에는 돈이 다 떨어질 때까지 아래 두 가지 액션 중 돈을 덜 쓰는 액션을 실행한다.

- 구매하지 않은 소들 중, 쿠폰 쓰지 않았을 때의 가격이 가장 낮은 소 가져오기

- 구매하지 않은 소들 중, 쿠폰 썼을 때의 가격이 가장 낮은 소를 가져오면서, 기존에 쿠폰으로 구매했던 소들 중 쿠폰을 사용하지 않았을 때 더 내야 하는 차액이 가장 적은 소에 대해 쿠폰 환불

여기까지가 풀이고, 우선 순위 큐 3개로 O(nlogn)에 구현할 수 있다. 

 

풀이 증명(+유도과정)은 조금 까다로운데, https://sharaelong.github.io/problem%20solving/2021/09/03/boj-5896/ 블로그에서 힌트를 많이 얻었다.

먼저, 이 문제는 MCMF문제로 환원할 수 있다. 각 소 하나마다 노드를 하나씩 할당하고, 각 소마다 no coupon / use coupon 두 개의 중간 노드로 잇는 간선이 있고, 이 간선들에 cost를 소를 살 때 필요한 돈 만큼 할당하는 방식이다. 예를 들면 예제는 대강 이렇게 그릴 수 있다.

 이렇게 cost에 상한이 있는 MCMF문제는 cost가 상한에 도달하기 직전까지 flow를 1씩 늘리면 가능한 최대 flow를 알 수 있다. 여기서 최대 flow가 곧 살 수 있는 최대 소 개수가 된다. 이 MCMF 모델링을 곧이곧대로 풀기에는 시간복잡도가 너무 크지만, flow를 흘리면서 최소 비용 경로를 찾았을 때 어떤 경로가 될지 생각해보면 위에서 설명한 정해와 똑같이 나온다.

- 쿠폰 개수만큼 flow를 흘리지 않았을 때는, 무조건 쿠폰을 사용하는 쪽으로 흘리는 것이 최소 비용 경로가 된다.

- 쿠폰 개수만큼 흘린 후에는, 쿠폰을 사용하지 않는 쪽으로 흘리거나, 쿠폰을 사용한 쪽으로 flow를 흘린 것을 취소하고 거기서 남은 flow를 다른 소 쪽으로 흘리는 것 둘 중 하나가 최소 비용 경로가 된다.

 

참고) 공식 풀이: http://www.usaco.org/current/data/sol_coupons.html