[백준 19939번] 박 터뜨리기 (C++)

문제링크 : https://www.acmicpc.net/problem/19939

19939번: 박 터뜨리기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, K, sum;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N >> K;

    for(int i=1; i<=K; i++) sum+=i;
    
    if(sum>N) cout << -1; //불가능한 경우
    else cout << (((N-sum)%K) ? K : K-1);
}

 

1~K까지 우선 누적합을 구해준다.

해당 누적합이 만약 N보다 크다면 나눠담을 수 없게 된다. 

따라서 이 경우 바로 -1을 출력해준다.

 

이제 가능한 경우에 대해서 체크해주어야 한다.

해당 경우에 대해서 다음과 같이 2가지 케이스가 존재한다.

<등차수열인 경우>
ex) 6 3 -> 1 2 3

<등차수열이 아닌 경우>
ex 7 3 -> 1 2 4

 

위 케이스는 사전에 구했던 누적합을 응용하여 계산이 가능하다.

현재 누적합은 등차수열인 상태이고, 현재 주어진 N에서 누적합만큼 빼면 추가로 몇개가 필요한지 알 수 있다.

만약 N-sum(누적합)이 1이면 추가로 1개를 더해주어야 하는 상황이다.

하지만 만약 바구니가 3개라면 기존 등차수열에 1만으로 등차수열을 유지할 수 없다.

(남은 나머지가 K로 나누어 떨어지지 않는 경우)

따라서 위 케이스 중 2번째인 <등차수열이 아닌 경우>가 된다.

(1, 2, 3 -> 1, 2, 4)

 

만약 N-sum이 3이면 추가로 3개를 더해주어야 하는 상황이다.

현재 바구니 갯수도 3이라면 기존 등차수열에 맞게 각 1개씩 더해주어 등차수열을 유지할 수 있다.

(남은 나머지가 K로 나누어 떨어지는 경우)

따라서 위 케이스중 1번째인 <등차수열인 경우>가 된다.

(1, 2, 3 -> 2, 3, 4)

 

이제 등차수열인 경우들과 등차수열이 아닌 경우들을 보면 다음과 같은 규칙이 존재하는 것을 알 수 있다.

<등차수열인 경우>
6 3
1, 2, 3
3-1 = 2 (K-1)

10 4
1, 2, 3, 4
4-1 = 3 (K-1)

-> 등차수열이면 K-1

<등차수열이 아닌 경우>
7 3
1, 2, 4
4-1 = 3 (K)

11 4
1 2 3 5
5-1 = 4 (K)
-> 등차수열이 아니면 K

 

따라서 등차수열이라면 [((N-sum)%K)==0] K-1를,

등차수열이 아니라면 [((N-sum)%K)!=0] K를 출력해주면 된다.