Educational Codeforces Round 20 D. Magazine Ad

http://codeforces.com/contest/803/problem/D

너무 간단한 파라메트릭서치문제이다. 보자마자 파라메트릭서치임을 알았는데 구현이 막혀서 1시간동안 풀이못했기에

반성하는 마음으로 기록용으로 글을 올린다..

(정확히는 파라메트릭서치가 아니라 바이너리 서치라는데 나는 파라메트릭서치가 편하다..)

공백, 하이픈(-), 알파벳 대소문자로 이루어진 문자열 한줄과 만들 수 있는 최대 줄 수 K를 입력받는다.

공백과 하이픈에서 줄을 바꿀 수가 있을 때 K줄을 넘지 않도록 하는 최대 가로폭(width) 를 구하는 문제이다.

가로폭은 각 줄의 길이중 최대인 길이를 말한다.

그럼 그냥 단순히 가로폭의 상한을 정해놓고 그 가로폭을 최대로 갖도록 최대한 한줄에 꾸겨넣을 때 줄의 수를

K개 이하로 만들 수 있는 지를 보아 파라메트릭을 돌리면된다.

근데 구현을 할 때에 신경을 써줘야 할 부분이 있다면 맨 마지막 줄의 끝은 공백이나 하이픈에 의해 나뉘는게 아니기 때문에

문자열의 길이가 1 적다는 것, 줄을 바꾸는 부분을 찾을 때에 공백이나 하이픈의 위치만을 봐줄 텐데

봐주다가 어느순간 limit(미리 정해놓은 가로폭) 을 넘는 순간 바로 이전 위치를 선택하여 줄바꿈을 해주어야 하는 부분,

그리고 애초에 인접한 두 줄바꿈가능위치(공백or하이픈의위치) 사이의 길이가 limit 보다 길어서 애초에 불가능한 경우를

따져주는 것이 포인트일 것이다. 그리고 이런 문제에서 신경을 곤두세워야 할 부분이(내가 자주 실수해서..)

구분자에 의해 나뉘는 중간 부분은 구현하는데 어려움이없는데 항상 맨 앞과 맨 끝부분을 잘 신경써줘야 예외가

발생하지 않는다는 것이다.. 나는 가로 길이를 계산할 때 prev 라는 변수를 사용하여 매번 '현재 - prev' 로 계산 하였는데

어떤 분은 덩어리의 크기를 다 계산해두어서 누적하는 식으로 하셨다. 이것은 구현상의 차이라 뭐가 맞다고 할 순 없으나

다양하게 생각해보는게 나을 것이고, 사실 이 두개 보다 훨씬 깔끔하고 안전하고 빠르고 신박한 구현 방법이 있을 것같지만

일단은 이쯤에서..

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;++i)
#define FOR(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
#define inp5(a,b,c,d,e) scanf("%d%d%d%d%d",&a,&b,&c,&d,&e)
#define fastio() ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;    
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<vector<int> > vvi;
typedef pair<int,pair<int,int> > piii;
typedef vector<piii> viii;
const double EPSILON = 1e-9;
const double PI = acos(-1);
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
const int MAX_N = 102;
 
string str;
int K;
vi cut;
bool possi(int w){
    int cnt = 0;
    int prev = -1;
    for(int i = 0 ; i < sz(cut); i++){
        if(cut[i] - prev - (i==sz(cut)-1) > w) {
            cnt++;
            if(i==0) return false;
            if(prev == cut[i-1]) return false;
            prev = cut[i-1];
            if(cut[i] - prev - (i==sz(cut)-1) > w) return false;
        }
    }
    cnt++;
    return cnt <= K;
}
int main() {
    scanf("%d\n",&K);
    getline(cin,str);
    str += ' ';
    int len = str.size();
    FOR(i,len) if(str[i] == ' ' || str[i] == '-') cut.pb(i);
    int lo = 0, hi = 1e8;
    while(lo<hi){
        int mid = (lo+hi) >> 1;
        if(!possi(mid)) lo = mid+1;
        else hi = mid;
    }
 
    printf("%d\n",lo);
 
    return 0;
}