블로그 옮겼습니다

BOJ 10919번 선물 상자 본문

Algorithm/Problem Solving

BOJ 10919번 선물 상자

sgc109 2017. 8. 7. 15:57

문제 링크


\(1 <= N <= 10^7\)

\(1 <= K <= N\)

\(1 <= L <= 10^9\)


원 모양에 L개의 구역이 있다. 나는 현재 구역0에 있고 구역0을 기준으로 시계방향으로

구역1, 구역2, ..., 구역L-1이 있다. 구역L-1다음은 다시 구역0으로 돌아온다.

즉, 구역L-1는 구역L-2와 구역0 과 인접한다. 인접한 구역으로 이동하는 데에는 1초가 걸린다.

N개의 팀이 임의의 구역에 있다. 이 N개의 팀 모두에게 선물을 나눠줘야한다.

선물은 0번구역에 넉넉하게 마련되어있다. 다만 한번에 들 수 있는 선물의 최대 개수는

K개이다.  이 때 모든 팀에게 선물을 한개씩 나눠주고 다시 0번 구역으로 돌아오는데 까지

걸리는 최소 시간을 구하는 문제이다.


이 문제는 그리디 + dp 로 풀 수가 있다.


우선 0번 구역에서 선물을 들고 일부 팀들에게 최적의 움직임으로 선물을 나눠주고 다시 0번 구역으로 돌아와서

선물을 재충전하고 다시 팀들에게 선물을 나눠주러 출발하는 것을 반복할 것이다.

그렇다면 이 최적의 움직임을 한 번 분류해보자. 조금만 생각해보면 딱 세가지 움직임 밖에 없음을 알 수가 있다.


<움직임 1>

<움직임 2>

<움직임 3>


우선 움직임 3을 보자 시계방향으로 돌던 반시계방향으로 돌던 어차피 걸리는 시간과

선물을 줄수있는 팀의 후보가 완벽하게 일치하기 때문에 방향은 상관이없다는 것을 알 수가 있다.

그리고 움직임 1을 보면 어떤 지점까지 갔다가 다시 왔던 길로 되돌아 오는 건데

구역 L/2를 넘어가는 순간 그냥 한바퀴 도는 것이 더 이득이기 때문에 이 터닝포인트는 무조건 0~L/2

라는 것을 알 수가 있다. 움직임2도 1과 방향만 다를 뿐 완벽하게 일치한다.


그렇다면 각각의 움직임에 대해 최적의 선물 배분법을 생각해 보자.

잘 생각해 보면 이동 거리가 같다면 기왕이면 멀리 있는 팀에게 우선적으로 선물을 나눠주는 것이 

유리하다는 것을 알 수가 있게 된다. 그리고 어차피 모든 팀에게 선물을 나눠 주어야 하기 때문에

가장 L/2 과 가까운, 즉 가장 먼 팀에게도 선물을 어차피 주어야 하므로 여기까지 어차피 와야하고

여기 까지 왔다가 다시 구역0으로 왔던길로 돌아오던, 한바퀴를 돌던 어쨌던 기왕이면 먼 팀에게 먼저

선물을 나눠주는게 낫다는 것을 알 수가 있다. 즉 무조건 먼팀부터 선물을 주도록 하자.

그런데 문제는 각 움직임의 횟수와 순서이다. 만약 횟수와 순서만 정해진다면 각 움직임에 선물을 주어야할

팀은 무조건 가장 멀리있는 팀들이기 때문에 누굴 주어야할지는 정해진다.


그럼 횟수와 순서를 어떻게 해야할까? 우선 잘 생각해보면 한바퀴를 도는 움직임3은 최대 한번밖에

할 필요가 없음을 알 수가있다. 왜냐하면, 움직임3을 두번해보자 그럼 2L의 시간이 걸리고 2K팀에게 선물을

나눠줄 수가 있다. 그런데 움직임1과 움직임2를 한번씩해보자. 그래도 똑같이 2K팀에게 선물을 나눠줄 수가 있지만

2L 이하의 시간이 걸리게 된다. 그렇기 때문에 움직임3을 X번 한다고 했을 때 X-2번으로 줄이고 

움직임1한번 움직임2한번을 더해주면 이득을 보면봤지 손해는 아니라는것이다. 그렇기 때문에 이 X가

2미만이 될 때까지 줄여주면 결국 움직임3은 최대 한번이된다.


그럼 일단 움직임3의 횟수는 결정났다. 그러면 움직임3의 순서는 어떻게 하면 좋을까?

직관적으로 생각했을 때 어차피 움직임3을 한번 한다고 정해졌으면 무조건 이 움직임3으로

먼저 가장 먼 K개의 팀들을 최대한 미리 나눠줘둬서 나쁠 것은 없다. 

그렇다면 움직임3을 할 때와 안할 때 두개로 나눠서 답을 구한뒤 최소를 취하면 답일 텐데

그럼 움직임 1,2는 몇번씩 해야할까? 이건 움직임3을 한다면 이 때 선물을 어떤 식으로 나눠주는지에 따라

자동으로 정해진다. 아까 움직임3에서 가장 먼 K개의 팀을 최대한 나눠준다고 했는데

구역 [0, L/2]와 구역 (L/2, L-1] 을 왼쪽, 오른쪽 이라고 표현한다면

왼쪽에서 가장먼놈 X명과 오른쪽에서 가장먼놈 K-X명을 움직임3으로 미리 나눠준다.

그러면 움직임 1,2로 나눠주어야 할 팀들이 정해지고 그러면 dp로 걸리는 시간을 계산할 수가 있다.


dp[i] : 구역0에서 가까운 순으로 팀들이 정렬되어있다고 가정할 때 i번 째 팀까지 나눠주는 데에 걸리는 시간

으로 두면

dp[i] = dp[i - K] + 2 * pos[i] (i > K)

와 같은 점화식이 나온다. 다만 가장 먼 팀부터 나눠주므로 기저를 아래처럼 잘 설정해주어야 한다.

dp[i] (i <= K) = 2 * pos[i]

왼쪽 반, 만 dp1로 구해두고 또 오른쪽 반만 dp2로 구해둔다.

팀들의 현재 위치에 대한 입력은 어차피 감소하지 않는 순서로 주어지기 때문에 따로 정렬할 필요 없이

L/2 보다 큰 팀에 대해서만 L 에서 빼주고 순서를 뒤집어주면 된다.

그럼 움직임3으로 미리 나눠주는 O(K) 개의 경우의수에 대해 미리 구해놓은 dp식으로 O(1)에 계산할 수가 있으므로

O(N)에 미리 전처리를 해두면 움직임3 할 때 O(1) 안할 때 O(K) 에 답을 계산할 수가 있으므로

전체 시간 복잡도는 O(N) 이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define fastio() ios_base::sync_with_stdio(0),cin.tie(0)
using namespace std;
typedef long long ll;
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
const int MAXN = 1e7;
vector<ll> pos;
ll posL[MAXN], posR[MAXN];
int N, K, L;
int main() {
    fastio();
    cin >> N >> K >> L;
    pos.resize(N);
    for(int i = 0 ; i < N; i++cin >> pos[i];
    
    auto s = upper_bound(all(pos), 0);
    auto m = upper_bound(all(pos), L / 2);
    
    vector<ll> ss = vector<ll>(s, m);
    vector<ll> ee = vector<ll>(m, pos.end());
    
    reverse(all(ee));
    for(int i = 0 ; i < sz(ee); i++) ee[i] = L - ee[i];
    
    for(int i = 0 ; i < sz(ss) && i < K; i++) posL[i] = ss[i] * 2;
    for(int i = 0 ; i < sz(ee) && i < K; i++) posR[i] = ee[i] * 2;
    for(int i = K ; i < sz(ss); i++) posL[i] = posL[i - K] + ss[i] * 2;
    for(int i = K ; i < sz(ee); i++) posR[i] = posR[i - K] + ee[i] * 2;
 
    ll ans = posL[sz(ss) - 1+ posR[sz(ee) - 1];
 
    for(int i = 0 ; i <= K; i++) {
        ll l = i >= sz(ss) ? 0 : posL[sz(ss) - 1 - i];
        ll r = K - i >= sz(ee) ? 0 : posR[sz(ee) - 1 - (K - i)];
        ans = min(ans, l + r + L);
    }
 
    cout << ans;
 
    return 0;
}
cs


Comments