[BOJ/백준][Silver5] 19939 : 박 터뜨리기 (C++)

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

19939번: 박 터뜨리기

 

 

[난이도] Silver5
[유형] Greedy

[풀이]
N을 1,2,3...,K 와 같이 등차수열 형태로 할당이 가능한 경우는 답이 K-1로 최적인 경우입니다.

1~K의 합인 K(K+1)/2 보다 N이 큰 경우에는
큰 수부터 1을 할당해주면 됩니다.
예를 들어
N이 13이고 K가 4일 때,
1,2,3,4 -> 10개를 사용했고 3개가 남았습니다.
1,3,4,5 -> 3개를 큰 수부터 차례로 1씩 할당하여 답은 K = 4입니다.

만약 K가 15라면
2,3,4,5 로 할당 하는 것이 가능하여 답은 K-1 = 3이 됩니다.

이와 같이 N-K(K+1)/2 가 K로 나누어 떨어지는 경에 답은 K-1이 되고,
아닌 경우에는 가장 큰 값에 1을 무조건 더해주어야 하므로 답은 K가 됩니다.

 

#include <cstdio>
using namespace std;
int N,K,ans;
int main(){
    scanf("%d%d",&N,&K);
    int sum=K*(K+1)/2;
    if(sum>N){
        puts("-1");
        return 0;
    }
    int a = N-sum;
    if(a%K) printf("%d",K);
    else printf("%d",K-1);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver5/19939.cpp