그리디한 접근법을 적용할 수 있는 문제이다. 간단히는 소의 숫자가 i+1인 경우의 최적해에서 고른 소가 i인 경우의 소를 항상 포함하기에 그리디한 접근이 가능하다고 보면 되겠다.
k개의 소를 구매할 때까지는, 쿠폰을 사용한 가격 중 낮은 순서부터 고르는 것이 최적임은 자명하다.
그 이후에는 2가지 경우가 있는데, 하나는 남은 소들 중 쿠폰을 적용하지 않았을 때 가장 싼 소를 가져가는 것이다.
또는 쿠폰을 사용하는 소를 추가해야 하는데, 쿠폰을 사용한 소들 중 하나를 쿠폰을 사용하지 않게 바꾸고 쿠폰을 사용하는 소를 추가해야 한다. (바꾸는 소를 고르는건 비용이 최소가 되도록 Priority Queue를 이용하자.)
이렇게 바꾸지 않을 경우, 보고 있는 소를 추가하는 것보다 지금 가지고 있는 소를 유지하면서 위의 경우를 사용하는 것이 낫기 때문이다. 다시 말해, 이미 쿠폰을 사용한 A라는 소가 있다고 하자. 시장에는 A보다 쿠폰가가 낮은 소가 없기에, A를 쿠폰을 사용하던 사용하지 않던 항상 데리고 있는 상태를 유지하는 게 최적이라는 것이다.
이제 소의 숫자를 늘려 가며 2가지 경우 중 더 사용하는 돈이 적은 걸 선택하면 된다.
(쿠폰을 사용한 소의 가격과 사용하지 않은 소의 가격을 각각 정렬해 두면 시간 내에 해결할 수 있다.)
사용한 돈이 M을 초과하지 않을 때까지 소를 추가하는 걸 반복하면 문제를 해결할 수 있다.
Solved.ac에서는 문제에 SCC태그를 달아놔서 쫄았는데, 풀어 보니 필요 없었다. P4라는 난이도도 부풀려진게 아닐까.
풀이로 넘어가서, 문제 상황만 보면 x_i를 데려가야 i를 데려갈 수 있기에, x_i에서 i로 간선을 연결하고 위상정렬을 하고 싶어진다. SCC가 있을 테니, 그걸 잘 처리하면 될 거 같다고 생각하게 된다.
이제 그래프의 형태를 관찰하면, In-degree가 하나니까 사이클이 하나 있고, 거기서 뻗어나가는 그래프가 만들어진다.
그 예시로 문제의 두번째 TC에 대한 그림은 다음과 같다.
즉, 이 사이클 전체가 버스에 타면 해당 컴포넌트에서 나머지 사람들은 원하는 수만큼 버스에 태울 수 있고, 아니라면 이 컴포넌트의 사람은 아예 태울 수 없다.
그러면 해당 컴포넌트의 크기와, 해당 컴포넌트에서 사이클의 크기를 알면 문제를 해결할 수 있을 것이다. 컴포넌트의 크기는 Disjoint Set으로 구한다. 사이클의 크기는, 위에서 만든 그래프를 뒤집고 위상정렬을 하면 남는게 사이클이기 때문에 그 크기를 구할 수 있다.
(즉, 애초에 x_i에서 i로 간선을 연결할 필요 없이 i에서 x_i로 간선을 연결하면 된다! 필자의 사고 흐름을 정리한 것이기 때문에 위의 그래프가 나왔지만, 반대 그래프를 그려야 문제를 해결할 수 있다는 것이다. 물론 필자와 다른 방법(DFS 등)으로 사이클을 찾을 경우 위의 그래프를 활용하는 것이 더 좋을 때도 있겠다.)
이제 마지막으로 답을 구하기 위해서는 [n][k]짜리 일종의 knapsack DP를 하면 된다. i번째 컴포넌트까지 확인하고, j명을 태워야 할 때 태울 수 있는 사람의 수의 최대값을 저장하는 것이다.
각각의 컴포넌트에 대해, 그 크기를 sz[i], 사이클 크기를 cyc[i]라 두면, 아래와 같은 점화식을 얻을 수 있다. i번째 컴포넌트의 사이클을 가져가거나, 가져가지 않을 수 있기 때문이다.
DP[i][j]=max(DP[i-1][j-cyc[i]]+sz[i], DP[i-1][j])
해당 DP를 수행하고, 마지막으로 데려갈 수 있는 사람의 수를 구할 때는 DP[n][j]의 최대값을 확인하면 답을 얻을 수 있다.
먼저 1명이 탈출한다고 생각해보자. BFS를 통해 Flood Fill을 돌리는데, 지나온 문의 개수가 0개일때, 1개일때, ... 순서대로 방문하면 된다.
구현은 각각의 위치를 방문할 때 인접한 위치가 비어 있으면 현재 사용중인 큐에 넣고, 문이면 다음 큐에 넣어서 BFS를 돌리는 방식으로 하였다. 각각의 위치에 몇번째 큐에서 방문하였는지를 기록하면 된다. 필자는 귀찮아서 큐 10000개로 처리하였지만, 큐2개로 잘 처리해도 해결할 수 있을 것이다.
감옥의 테두리에서 몇번째 큐에서 방문하였는지가 탈옥 과정에서 연 문의 수가 된다. 이것의 최소값을 찾으면 1명짜리 문제는 해결된다.
이제 2명이 탈출하는 경우를 따져야 하는데, 2가지 경우를 생각해야 한다.
1. 두 명이 따로 탈출하는 경우
2. 두 명이 탈출하는 중에 만나는 게 가능한 경우
1은 두 사람에 대해 위의 내용을 처리하고 두 값을 합하면 된다.
2는 임의의 지점을 잡아 그 지점에서 만나서 바깥으로 나간다고 생각하면 된다. 이 부분을 해결하기 위해서는 감옥의 테두리 지점들을 보면서 빈 공간이면 첫번째 큐에, 문이면 두번째 큐에 넣고 시작하는 BFS를 하나 더 돌려서 총 3번의 BFS를 돌렸다. 그리고 각 지점을 보면서 그 지점이 만나는 지점이라고 생각해 3개의 BFS에서 얻어진 값을 더하면 되는 것이다.
마지막으로 이 지점이 문인지 아닌지에 대해 처리를 해주자. 문이면 3번 카운트되므로 2를 빼야된다.
1번째 TC에 대해 해당 풀이를 적용한 그림은 다음과 같다.
1번째 죄수에 대한 BFS바깥에서 보는 BFS
표시한 지점에서 세 BFS의 값을 합한 값이 6이고, 해당 지점이 문이므로 2를 빼면 4가 얻어진다. 이게 최소라 해당 TC의 답은 4가 된다.
k를 매개변수로 잡고 차이가 k보다 작거나 같도록 만들 수 있는지에 대해 파라메트릭 서치를 하면 된다.
그러면 k가 주어졌을 때 그 여부를 알아내는 알고리즘을 작성해야 하는데, 이는 다익스트라에서 아이디어를 구했다. 전부 우선순위 큐에 때려박고, 작은 지점부터 보면서 양쪽에 k보다 차이가 큰 지점이 있으면 그 지점을 낮춰 주고 Update하고 큐에 넣으면 된다. 각 과정에서 사용된 연산의 수를 합해서 T와 비교하면 된다. 이렇게 하면 다익스트라와 비슷한 방식으로 낮추는 과정에서 문제가 생기지 않는다.
2018년 당시 서브태스크만 긁었던 문제. 당시에 생각한 아이디어 자체는 맞았기에 쉽게 AC를 받을 수 있었다.
어느 한 칸의 물의 높이가 정해졌다고 생각하면, 그 칸보다 높은 인접한 칸을 따져 줄 때 크게 세 가지 경우가 있을 것이다. 두 칸 사이에 인접한 칸의 현재 상태보다 낮은 구멍이 없거나, 구멍이 두 칸의 높이 사이에 있거나, 구멍이 주어진 칸의 높이보다 낮은 경우이다. 첫번째 경우는 업데이트를 하지 않으면 되고, 두 번째 칸의 경우는 구멍의 높이로 업데이트 해주고, 세번째 경우는 주어진 높이로 업데이트하면 된다.
높이가 낮은 순서대로 우선순위 큐에 넣어 따져 줄 칸을 정할 수 있고, 다익스트라랑 비슷한 아이디어이므로 이렇게 관리하면 된다는 증명도 비슷하게 할 수 있다.
거리 대신 물의 높이를 기준으로 다익스트라를 구현하고, dis[i]+d[i][j]를 쓰는 대신 max(h[i], d[i][j])로 업데이트를 해 주면 쉽게 AC를 받을 수 있다.
