[Codeforces 1110B] Tape

[Codeforces 1110B] Tape

요즘 그리디문제를 자꾸 바이너리 서치로 풀려고 삽질하는 것 같다. 그리디 문제는 솔루션이 그리디라는 것만 알면 쉬운데, 확신이 없어서 헤매는 것 같다.

길이가 m인 긴 막대에 n개의 부서진 부분이 존재한다. 이 부서진 부분을 붙이기 위해 총 k개의 테이프를 사용할 수 있을 때(한 개당 테이프 길이는 상관없음) 필요한 총 테이프 길이의 최소는 얼마인지를 묻는 문제이다. 문제는 보기에는 바이너리 서치의 lower bound로 풀면 될 것 같은데 WA를 받았다. 아마 반례가 존재하는 모양인데 아직 정확히 왜 안되는지는 모르겠다. 아무튼 더 확실한 그리디 풀이법이 있으니 그리디로 풀자.

사실 이 문제를 간단하게 표현하자면 n개의 인접한 수를  k개의 그룹으로 묶을 때 그룹 내 원소의 최대값과 최소값의 차들의 합이 최소가 되도록 하는 문제와 같다(마지막에 +k를 해주어야 하긴 한다). 여기서 핵심은 'n개의 수 인접한 수를 k개의 그룹으로 묶는다'이다. k개의 그룹으로 묶기 위해서는 (n-k)개 간격을 서로 붙여주면 된다. 예를 들어 n=5,k=3이고 ( 1 2 3 4 5 ) 라는 수열이 있다면 (n-k)인 2개의 간격(3개의 수)을 이어주면 된다. [1,2],[2,3]을 잇는다면 [1,2,3],[4],[5]가 된다. 즉 이 문제는 전체 (n-1)개의 간격 중에서 (n-k)개의 간격을 선택해서 그 간격의 합을 최소화 하면 된다. 그 방법은 당연히 a[i+1]-a[i]값을 저장해서 정렬한 뒤 (n-k)개 만큼 뽑아내면 된다. 마지막에 k를 더하는 것은 문제에서 1~2를 잇기 위해서는 테이프의 길이가 1이 아닌 2가 필요하기 때문이다. 

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stdlib.h>
#include<stack>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
/****************************Default Template******************************/
#define SIZE 100009
// #define IMP
// #define INF
// const int MOD=
struct S{
    int a,b;
 
    S(){}
    S(int _a,int _b){
        a=_a;
        b=_b;
    }
 
    const bool operator<(const S &o) const{
        return a<o.a;
    }
};
priority_queue<int> pq;
priority_queue<int,vector<int>,greater<int>> mpq;
map<int,int> mp;
stack<int> st;
set<int> set_i;
/****************************Default Template******************************/
 
 
 
int arr[SIZE],gap[SIZE];
int main(){
    int n,m,k;    scanf("%d %d %d",&n,&m,&k);
 
    for(int i=1 ; i<=n ; i++)
        scanf("%lld",&arr[i]);
 
 
    for(int i=1 ; i<n ; i++){
        gap[i]=arr[i+1]-arr[i];
    }
 
    sort(gap+1,gap+n);
    int ans=0;
    for(int i=1 ; i<=n-k ; i++)
        ans+=gap[i];
    ans+=k;
    printf("%d\n",ans);
 
    return 0;
}