[백준,c++] 19939번 - 박 터뜨리기

문제

19939번: 박 터뜨리기

 

코드

#include <iostream>
#include <vector>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N, K; cin>>N>>K;
    int sum = (K * (K+1)) / 2;  // 등차수열 합
    
    if(sum > N) cout << -1;
    else if((N - sum) % K == 0) cout<< K - 1;
    else cout<< K;
}

 

풀이

일단 실버 5 문제라서 풀이 자체는 간단하지만 그 간단한 풀이를 떠올리는 게 굉장히 오래 걸렸습니다. 조금 더 높아도 될 것 같은데 ...

일단 K개의 바구니에 전부 개수가 다르게 담아야 하기 때문에 각각의 바구니에 담을 수 있는 수는 K가 3일때 3, 2, 1 이런식으로 연속적인 갯수일때 최대로 담을 수 있습니다. 따라서 등차수열을 통해 해당 수열의 합이 N보다 클 경우는 담을 수 없는 경우가 되기에 바로 -1을 출력합니다. 

그리고 연속적으로 담고 남은 공의 갯수가 K개로 깔끔하게 마무리가 될 경우는 K-1, 아닐 경우 K를 출력합니다.

아래는 제가 만들어낸 테스트 케이스들 입니다.

7 3
4 2 1 (3)
	
6 3
3 2 1 (2)

5 2
3 2 (1)

4 2
3 1 (2)

4 3
x ( -1)

6 2
4 2 (2)

3 2
2 1 (1)