[백준 - C#] 11939번 박 터뜨리기

문제링크

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

19939번: 박 터뜨리기

 

문제

 K개의 팀이 박 터트리기 게임을 한다. 각 팀은 하나의 바구니를 가지고 있고, 바구니에 들어있는 공을 던져서 자기 팀의 박을 터트려야 한다.
우리는 게임을 준비하기 위해서, N개의 공을 K개의 바구니에 나눠 담아야 한다. 이때, 게임의 재미를 위해서 바구니에 담기는 공의 개수를 모두 다르게 하고 싶다. 즉, N개의 공을 K개의 바구니에 빠짐없이 나누어 담는데, 각 바구니에는 1개 이상의 공이 있어야 하고, 바구니에 담긴 공의 개수가 모두 달라야 한다.
게임의 불공정함을 줄이기 위해서, 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이가 최소가 되도록 담을 것이다.
공을 바구니에 나눠 담기 위한 규칙을 정리하면 다음과 같다.
 N개의 공을 K개의 바구니에 빠짐없이 나누어 담는다.각 바구니에는 1개 이상의 공이 들어 있어야 한다.각 바구니에 담긴 공의 개수는 모두 달라야 한다.가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이가 최소가 되어야 한다.
위의 규칙을 모두 만족하며 N개의 공을 K개의 바구니에 나눠 담을 때, 나눠 담을 수 있는지 여부를 결정하고, 담을 수 있는 경우에는 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이를 계산해서 출력하는 프로그램을 작성하시오.

조건

시간제한 : 0.25초
메모리 제한 : 512 MB

입력

첫 번째 줄에 공의 개수를 나타내는 N$N$과 팀의 수를 나타내는 정수 K$K$가 주어진다.

출력

 N개의 공을 K개의 바구니에 문제의 규칙을 만족하면서 나눠 담을 수 있다면, 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이를 출력한다. 나눠 담을 수 없는 경우에는 -1을 출력한다.

 

문제정리

1. N개의 공을 K개의 바구니에 빠짐없이 나누어 담는다.
2. 각 바구니에는 1개 이상의 공이 들어 있어야한다.
3. 각 바구이네 담긴 공의 개수는 모두 달라야 한다.
4. 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이가 최소가 되어야한다.

이 문제의 경우 바구니에 1개이상 공이 무조건 들어야 있어야 하기때문에 1개씩 담고 시작하자 라고 생각을 한 후 그다음 모든 바구니의 개수가 달라야하며 공의 개수가 최소가 되어야 하기 때문에 순차적으로 바구니에 공을 담자고 생각하였습니다.

그리하여 나온 방법은 1부터 K개 까지 바구니에 담는 것입니다.

예를들어 5 3의 경우 바구니가 3개이기 때문에 1,2,3 으로 담고 10, 4의 경우 1,2,3,4로 담고 시작하였습니다.

 

그 다음 등차수열로 1부터 K개의 합을 다 더하고 난 값으로 N가 비교하게 되면 나눠 담을 수 없는 경우에 수를 구할 수 있습니다.

 

나눠 담을 수 있는경우에는 두가지가 있는데, 동일한 개수로 분배할 경우와 동일하지 않게 분배할 경우 입니다.

(N-sum) % K == 0 이라면 K개의 바구니에 동일하게 분배가 가능하기 때문에 최대 값과 최소갑의 차이는 K-1 개이며

 

동일 하지 않을 경우는 K개 입니다.

C# 코드

static void Main(string[] args)
{
    StreamWriter writer = new StreamWriter(OpenStandardOutput());
    StreamReader reader = new StreamReader(OpenStandardInput());
 
    string[] input = reader.ReadLine().Split();
    int N = int.Parse(input[0]);
    int K = int.Parse(input[1]);
 
    // 등차수열의 합
    // 1부터 K까지의 총합
    int sum = K * (K + 1) / 2;
 
    if (N < sum) // 필요한 박의 개수가 N보다 크다면 -1 출력
        writer.WriteLine(-1);
    else if ((N - sum) % K == 0) // 동일한 개수로 분배를 할 수 있다면 제일 큰수와 제일 작은수의 차이는 K-1이 됩니다.
        writer.WriteLine(K - 1);
    else
        writer.WriteLine(K); // 그게 아니라면 제일 큰수와 작은수는 K개 만큼 차이납니다.
 
    writer.Close();
    reader.Close();
}

읽어주셔서 감사합니다 오늘도 즐거운 하루 되세요.