박 터뜨리기( BOJ 19939 )

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

19939번: 박 터뜨리기

 

문제 파악하기

N개의 공을 조건에 맞게 K개의 바구니에 넣었을 때, { 가장 공이 많은 바구니 - 가장 공이 적은 바구니 }의 최솟값을 구하는 문제입니다. 조건은 까다롭지 않습니다. N개의 공이 모두 들어가야하고, K개의 바구니에는 적어도 1개 이상의 공이 들어가야 하며, 어느 바구니에도 동일한 개수의 공이 들어갈 수 없습니다. 3가지 조건을 만족하는 여러 가지 경우 중 공이 가장 많은 바구니와 가장 적은 바구니의 차이가 최소가 되기 위해서는 문제를 추상화시켜야 합니다.

 

문제 해결하기

단순히 모든 경우의 수를 구하기에는 나올 수 있는 경우의 수가 너무 많습니다. 따라서 이 문제를 조금은 단순하게 추상화시켜 문제에 숨겨진 규칙을 찾아야 합니다. 가장 단순하게 추상화시키는 방법은 바구니에 들어있는 공의 개수로 문제를 표현하는 방법이 있습니다. 이 상태에서 6개의 공을 3개의 바구니에 넣는 방법은 어떤 것이 있을까요? F(N, K)를 문제에서 주어지는 함수라고 할 때, 다음과 같이 바구니에 공을 넣을 수 있습니다.

 F(6, 3) = { 1, 2, 3 }

 

그리고 결괏값은 2를 출력하게 됩니다. 그렇다면 F(7, 3)은 어떨까요?

F(7, 3) = { 1, 2, 4 }

 

결괏값은 3을 출력하게 됩니다. F(8, 3)도 한번 확인해보겠습니다.

F(8, 3) = { 1, 3, 4 }

 

이 때에는 3을 출력합니다. 여기까지 함수들을 살펴보면서 공통점을 찾았나요? 사실 위 3개 함수의 결괏값은 모두 { 1, 2, 3 }에서 만들어집니다. F(7, 3)의 경우, { 1, 2, 3 }의 숫자 중 3을 4로 변환한 값입니다. F(8, 3)인 경우에는 { 1, 2, 3 }의 숫자 중 2를 4로 변환한 값입니다. 그럼 이 상태에서 F(9, 3)과 F(10, 3)은 어떻게 될까요?

F(9, 3) = { 2, 3, 4 } / F(10, 3) = { 2, 3, 5 }

 

F(9, 3)의 경우, F(6, 3)에서 모든 숫자에 1씩 더한 걸 볼 수 있습니다. 그리고 F(10, 3)은 F(9, 3)에서 4가 5로 증가된 걸 볼 수 있습니다. 결국 모든 F(N, K)는 연속된 K개의 숫자 혹은 연속된 K개의 숫자 중 1개의 숫자가 변환된 형태라는 걸 알 수 있습니다. 그렇기에 모든 결괏값은 (K-1) 또는 K를 가지게 된다는 점도 알 수 있습니다. 만약 F(N, K)가 연속된 K개의 숫자로 표현할 수 있다면 (K-1)값을, 아니라면 K값을 가지게 된다는 걸 유추할 수 있기 때문입니다. 그럼 우리는 F(N, K)가 연속된 K개의 숫자로 표현할 수 있는지만 확인하면 되겠네요.

 

연속된 K개의 숫자로 표현될 수 있는지는 0부터 (K-1)까지의 누적합으로 알 수 있습니다. 만약 어떤 숫자가 a~(a+K-1)까지 연속된 숫자로 표현되었다면 해당 숫자의 누적합은 다음과 같이 표현될 수 있습니다.

a + (a+1) + ... + (a+K-1) = K*a + (0+1+...+(K-1)) = K*a + K*(K-1)/2

 

위의 식에서 0부터 (K-1)까지의 누적합을 빼면 다음과 같은 식을 도출할 수 있습니다.

K*a + K*(K-1)/2 - K*(K-1)/2 = K*a

 

K*a는 결국 K의 배수를 의미합니다. 그리고 연속된 숫자들의 합은 결국 전체 공의 개수인 N을 의미합니다. 따라서, N에서 (K-1)까지의 누적합을 뺀 값이 K의 배수인지 아닌지 확인하면 우리는 문제를 해결할 수 있습니다.

 

소스코드

#include <stdio.h>
 
int N, K, sum;
 
int main() {
    // input
    scanf("%d %d", &N, &K);
 
    // 누적합
    sum = K*(K+1)/2;
 
    if(sum > N) printf("-1");
    else {
        // 연속된 숫자로 누적합을 만들 수 있는 경우
        if((N-sum)%K == 0) printf("%d", K-1);
 
        // 만들 수 없는 경우
        else printf("%d", K);
    }
}

후기

직관력을 요하는 문제라고 생각합니다. 구현은 간단하지만 알고리즘은 나름 생각을 해야 하는 문제이기에 정올에 어울리는 문제라고 생각합니다.