(C++) - 백준(BOJ) 19939번 : 박 터뜨리기

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

19939번: 박 터뜨리기

공식을 찾아 푸는 수학문제였습니다.

 

📕 풀이방법

📔 입력 및 초기화

n, k 선언 후 입력받습니다.

 

📔 풀이과정

겹치지 않으면서 최소 1개를 바구니에 배분해야하므로 1, 2, 3, .... , x 가 k개의 바구니에 담겨있는 모양이 됩니다. 

\sum_{1}^{x} p = n 이라는 공식이 성립합니다.

\sum_{1}^{x} p = k(k+1)/2 = n 이 배분할 수 있는 최저 조건입니다.

 

 

📔 정답출력

1. n보다 누적합한 값이 더 작다면 배분할 수 없는 경우이므로 -1을 출력합니다.

2. n - 누적합의 값으로 적절히 배분했을 때를 생각하면 (n - 누적합 % k)인 경우와 그렇지 않은 경우로 나뉩니다.

이 차이를 diff라고 하면 diff % k == 0인 경우에는 k - 1를 출력합니다.

아닌 경우에는 k를 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n, k;
int main(){
    cin >> n >> k;
    ll diff = 2 * n - k * (k + 1);
    if(2 * n < k * (k + 1) ) cout << -1;
    else if(diff % k == 0) cout << k - 1;
    else cout << k;
}