[AtCoder - ARC101 C] Candles

난이도: 947

 

태그

• Sliding Window

 

풀이

1. \( K \)개의 초가 결정되었을 때, 이를 최소한의 시간을 써서 켜는 방법은?

선택된 \( K \)개의 초 중, 맨 왼쪽에 있는 초 \( x_1 \)과 맨 오른쪽에 있는 초 \( x_K \)를 생각해봅시다.

 

이 두 초는 선택된 초이므로 반드시 켜야 합니다.

그런데, \( x_1 \)을 켜러 가는 길에서 + \( x_K \)를 켜러 가는 길에서 다른 초들 \( x_2, x_3, \ldots, x_{K-1} \)을 모두 만나게 되기 때문에, 실제로는 \( x_1 \)과 \( x_K \)만 고려하면 됩니다.

 

그럼 실제로는 얼마나 걸릴까요? 이는 두 초의 방향에 따라 달라집니다.

• 만약 \( x_1 \)과 \( x_K \)이 출발점을 기준으로 같은 방향에 있다면:
  더 멀리 있는 초를 켜러 가는 과정에서 다른 모든 초를 만날테므로, \( \max(|x_1|, |x_K|) \)의 시간이 걸립니다.
• 만약 \( x_1 \)과 \( x_K \)이 출발점을 기준으로 다른 방향에 있다면:
  \( x_1 \)까지 갔다가 \( x_K \)까지 까지 가야 하므로, 중간에 출발점을 지나야 합니다.
  이 때 걸리는 시간은 \(|x_1| + |x_1 - x_K| \)의 시간이 되겠죠.
  물론 실제로는 \( x_K \)를 먼저 가는 방법도 있으니, \( \min(|x_1|, |x_K|) + |x_1 - x_K| \)가 됩니다.

 

2. 켜야 하는 \( K \)개의 초는 어떻게 결정할까?

초를 켜러 가는 과정에서 건너뛰는 초가 있다고 생각해봅시다.

그럼, 그 초를 안 켰기 때문에 다른 초를 켜기 위해 더 먼 길을 떠나야 합니다.

이는 당연히 최적이 아니겠죠.

 

즉, \( K \)개의 연속된 초를 켜는 경우만 고려하면 됩니다.

 

// 좀 더 엄밀한 증명을 원한다면, [1]에서 나온 수식을 생각해보세요.

// \( x_1 \)과 \( x_K \)의 거리를 최소화하려면 \( K \)개를 연속으로 선택해야 한다는 것이 자명해질 겁니다.

 

3. 코드

ll arr[100020];
 
void Main(){
    int n, k; cin >> n >> k;
    for (int i = 1; i <= n; i++){ cin >> arr[i]; }
    ll ans = 1e18;
    for (int ed = k; ed <= n; ed++){
        int st = ed-k+1;
        ll d1 = abs(arr[st]), d2 = abs(arr[ed]);
        if (sgn(arr[st])*sgn(arr[ed]) == -1){ ans = min(ans, d1+d2 + min(d1,d2)); }
        else{ ans = min(ans, max(d1,d2)); }
    }
    cout << ans;
}