BOJ 2613: 숫자구슬

https://www.acmicpc.net/problem/2613

2613번: 숫자구슬

처음 문제를 보고 이분 탐색을 이용한다면 문제를 쉽게 해결할 수 있으리라 생각하고 구현한 후 제출하였다.

그 방법은 먼저 최댓값의 최솟값을 결정한 후, 해당 값을 이용하여 배열을 돌며 구간의 합이 해당 값보다 작게 그룹을 만들어서 그 그룹의 수와 주어진 m을 비교하는 방법을 이용하였다.

오랜만에 문제를 풀어서 그런지 테스트 케이스 이외의 다른 케이스들을 고려하지 않고 그냥 제출을 하였다.

 

먼저 틀렸습니다를 받았다.

이유를 찾기 위해 다양한 케이스들을 넣어봤지만 찾는데 제법 걸렸다. 다음과 같은 테스트 케이스를 넣는 경우 딱 맞는 그룹의 수를 찾지 못한다.

5 4
1 1 1 1 1

이유에 대해 생각해보니 최댓값이 2라고 가정한다면 그룹의 수가 3이 나오고, 최댓값이 1이라고 가정한다면 그룹의 수가 5가 나오기 때문에 딱 맞게 그룹을 나눌 수 없기 때문이었다.

그렇다면 '이 문제를 어떻게 하면 해결할 수 있을까?' 라고 고민해보다가 다음과 같은 방법을 떠올렸다.

• 먼저 이전과 같은 방법으로 이분 탐색을 이용하여 답을 찾는다.
• 이분 탐색 도중 답이 없는 경우를 대비하여 구하고자 하는 그룹의 수(m)와 가장 차이가 덜 나는 그룹의 수를 저장한다.
• 해당 값을 저장하며 문제에서 구하고자 하는 최댓값의 최솟값을 구하기 위해 해당 값을 계속해서 갱신해준다.
• 마지막에 답을 출력하는 부분에서 정답이 있다면 그대로 출력한다.
• 만약 정답이 없다면 2개 이상으로 묶여있는 그룹을 하나씩 풀어준다.
• 그룹을 풀어줄 때 이분 탐색을 하며 구해놓은 구하고자 하는 그룹의 수와 차이 값을 이용하여 풀어준다.

사실 볼드체로 해놓은 부분이 아직까지도 아리송한 느낌이다.

먼저 이미 묶여있는 그룹을 풀어주는 과정에서 이미 구해놓은 최댓값의 최솟값이 줄어들지는 않을까라는 생각을 했다. 어떻게 하면 확실하게 최댓값의 최솟값이 줄어들지 않게 만들 수 있을까라고 생각을 해보던 중, 어차피 그 값이 줄어들어서 답이 나올 수 있는 경우라면 이미 이분 탐색을 통해 답을 구했을거라고 생각하고 넘어가기로 하였다.

 

코드는 조금 지저분하게 짜놔서 나중에 수정을 해야겠다.

#include<bits/stdc++.h>
using namespace std;
vector<int> seq;
int chk(int mid){
  int prev = 0, cur = 0, res = 1;
  for(int i = 0; i<seq.size(); ++i){
    cur += seq[i];
    if(cur - prev > mid){
      prev = cur - seq[i];
      ++res;
    }
  }
  return res;
}
int main(){
  int n, m; scanf("%d %d" ,&n, &m);
  seq.resize(n);
  int M = 0;
  for(int i = 0; i<n; ++i){
    scanf("%d", &seq[i]);
    M = max(M, seq[i]);
  }
  if(m == n){
    printf("%d\n", M);
    for(int i = 0; i<n; ++i)
      printf("%d ", 1);
      return 0;
  }
  int l = 0, r = 1e9, res = 1e9;
  int noAns = 1e9, noAnsMid = 1e9;
  while(l <= r){
    int mid = (l + r) >> 1;
    int c = chk(mid);
    if(c <= m){
      r = mid - 1;
      if(c == m)
        res = min(res, mid);
    }
    else
      l = mid + 1;
    if(abs(c - m) <= noAns){
      if(abs(c - m) == noAns){
        noAnsMid = min(noAnsMid, mid);
      }
      else{
        noAns = abs(c - m);
        noAnsMid = mid;
      }
    }
  }

  vector<int> ls;
  int cur = 0, prev = 0, cnt = 0;
    for(int i = 0; i<seq.size(); ++i){
     cur += seq[i];
     if(cur - prev > (res == 1e9 ? noAnsMid : res)){
       prev = cur - seq[i];
       ls.push_back(cnt);
       cnt = 0;
     }
     ++cnt;
    }
    if(cnt)
      ls.push_back(cnt);
  if(res == 1e9){
    printf("%d\n", noAnsMid);
    vector<int> tmp;
    for(int i = 0; i<ls.size(); ++i){
      if(ls[i] > 1 && noAns){
        noAns--;
        printf("%d %d ", ls[i] - 1, 1);
      }
      else
      {
        printf("%d ", ls[i]);
      }
      
    }
  }
  else{
    printf("%d\n", res);
    for(auto i : ls)
      printf("%d ", i);
  }
}