[백준] 19939. 박 터뜨리기 (2020 정올 초등부 1번) <C++>

www.acmicpc.net/problem/19939

19939번: 박 터뜨리기

 

 

규칙을 찾는 문제였다.

 

규칙만 찾는다면 구현은 금방 하는 문제이지만 규칙 찾기가 쉽지 않았다.

 

 

 

우선 공을 가장 적게 분배해준다. 1)

 

k = 3이라면

 

1 2 3  <- 이런 식으로

 

1부터 k까지의 누적합이 n보다 크다면 불가능한 경우다. 2)

 

 

 

가능한 경우,

 

두 가지의 경우로 나뉜다.

 

ex. 6 3

- 1 2 3

 

ex. 9 3

- 2 3 4

 

ex. 10 4

- 1 2 3 4

 

위의 세 예시처럼 연속적인 수들로 담을 수 있는 경우와

 

ex. 7 3

- 1 2 4

 

ex. 11 3

- 2 4 5

 

ex. 11 4

- 1 2 3 5

 

위의 예시처럼 연속적이지 못한 수들로 담을 수 있는 경우

 

이렇게 두 가지로 나뉜다.

 

 

 

전자의 경우 k-1이 정답이고 3)

 

후자의 경우 k가 정답이 된다. 4)

 

라는 규칙을 찾아볼 수 있다.

 

 

 

// 정답 코드

#include <iostream>
using namespace std;
 
int main() {
   int n, k, i;
   int sum = 0;
 
   cin >> n >> k;
   for (i = 1; i <= k; i++) {  //1)
      sum += i;
   }
   n -= sum;
 
   if (n < 0) {  //2)
      cout << -1;
   }
   else {
      if (n % k == 0)  //3)
         cout << k - 1;
      else if (n % k != 0)  //4)
         cout << k;
   }
}