[백준 19939] 박 터뜨리기

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

Constructive한 문제였다. 하지만 그리 어려운 문제는 아니였다.

1. 풀이

기본적으로 \(1\;2\;3\;4\;...\) 이런 식으로 분배하는 것이 최선이다. 그렇기 때문에 \(n\)이 \(k(k-1)/2\)개 보다 작다면 \(-1\)이다.

 

만약 \(1\;2\;3\;4\;...\) 이런식으로 분배했다고 치자. 그러면 \(n\)이 \(0\)일 때에는 답은 \(k - 1\)이다.

하지만 \(n\)이 남았다면? 제일 큰 \(4\;3\;2\;1\;...\) 이런 내림차순으로 \(1\)개씩 더해주는 것이다. 그리고 첫번째 원소와 마지막 원소의 차가 곧 답이다.

 

이 방식이 왜 시간안에 돌아가냐면 \(k = 1000\)일 때 필요한 공의 개수는 \(50\)만개 정도이다. 하지만 공은 \(10\)만까지 밖에 들어오지 않으므로 정말 최악의 경우에도 \(10\)만번까지만 돌아간다.

 

정해는 수학 공식 하나로 끝난다. 내 풀이는 그냥 이런식으로도 풀 수 있구나 라고만 생각해주길 바란다.

2. 소스코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
 
using namespace std;
int main() {
    int n, k; cin >> n >> k;
    vector<int> arr(k);
 
    bool flag = false;
    int cnt = 1;
    for(int i=0; i < k; i++){
        if(cnt > n) {
            flag = true;
            break;
        }
        arr[i] = cnt;
      n -= cnt;
        cnt++;
    }
    
    if(flag){
        cout << "-1";
        return 0;
    }
    
    while(n > 0){
            for(int i=k-1; i >= 0; i--){
                if(n == 0) break;
                arr[i]++;
                n--;
            }
    }
        
    
    if(n == 0 || k % n == 0){
    cout << *max_element(arr.begin(), arr.end()) - *min_element(arr.begin(), arr.end());
    }
    else
        cout << "-1";
    
    return 0;
}