[백준 - C#] 1052번 물병

문제링크

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

1052번: 물병

 

문제

지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번에 K개의 물병을 옮길 수 있다. 하지만, 지민이는 물을 낭비하기는 싫고, 이동을 한 번보다 많이 하기는 싫다. 따라서, 지민이는 물병의 물을 적절히 재분배해서, K개를 넘지 않는 비어있지 않은 물병을 만들려고 한다.

물은 다음과 같이 재분배 한다.

먼저 같은 양의 물이 들어있는 물병 두 개를 고른다.
그 다음에 한 개의 물병에 다른 한 쪽에 있는 물을 모두 붓는다.
이 방법을 필요한 만큼 계속 한다.

이런 제약 때문에, N개로 K개를 넘지않는 비어있지 않은 물병을 만드는 것이 불가능할 수도 있다.
다행히도, 새로운 물병을 살 수 있다. 상점에서 사는 물병은 물이 1리터 들어있다.

예를 들어, N=3이고, K=1일 때를 보면, 물병 3개로 1개를 만드는 것이 불가능하다. 한 병을 또다른 병에 부으면, 2리터가 들어있는 물병 하나와, 1리터가 들어있는 물병 하나가 남는다. 만약 상점에서 한 개의 물병을 산다면, 2리터가 들어있는 물병 두 개를 만들 수 있고, 마지막으로 4리터가 들어있는 물병 한 개를 만들 수 있다.

조건

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

입력

첫째 줄에 N과 K가 주어진다. N은 107보다 작거나 같은 자연수이고, K는 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 상점에서 사야하는 물병의 최솟값을 출력한다. 만약 정답이 없을 경우에는 -1을 출력한다.

 

문제정리

1. K개를 넘지 않는 비어있지 않은 물병을 만든다.
2. 같은 양의 물이 들어 있는 물병만 물을 재분배 할 수 있다.
3. 상점에서 물 1리터 담아있는 물병을 살 수 있다.
4. 상점에서 사야하는 물병의 최솟값을 구하자.

이번 문제의 경우 규칙을 찾고 그리디 알고리즘으로 문제풀이를 진행하였습니다.

아래 표와 같이 입력받은 N에 따른 남은 물병의 개수를 정리한 것입니다.

N	합친 물의 값	남은 물병의 개수
1	1	1
2	2	1
3	2 1	2
4	4	1
5	4 1	2
6	4 2	2
7	4 2 1	3
8	8	1
9	8 1	2
10	8 2	2
16	16	1

K는 항상 0보다 크기 때문에 남은 물병의 개수가 1인 값들은 상점에서 살 필요가 없기때문에 답이 0이 됩니다.

만약 남은 물병의 개수가 1이아닌 2나 3 등등 그보다 큰 수들은 입력받은 K의 값에 따라 상점에서 물병을 사거나 물병은 안사도되는 경우의수가 생깁니다.

 

예를들어 N이 7인 경우 K의 값이 2라면 물병 한개를 더사서 남은 물병의 개수를 줄여야 합니다.

 

정리하자면 N의 값을 2로 나누어 남은 나머지가 0이거나 0이 아닐 때의 경우에 따라 남은 물병의 개수를 계속 카운팅하고 더이상 나눌 값이 없다면 K의 값과 비교하여 물병의 개수가 맞는지 파악하고 아니라면 물병을 하나 사서 다시 위와 같은 작업을 진행합니다.

 

나머지 부분은 코드와 주석을 보며 파악하시면 쉽게 이해가 되실 것 같습니다.

 

C# 코드

static void Main(string[] args)
{
    StreamWriter writer = new StreamWriter(Console.OpenStandardOutput());
    StreamReader reader = new StreamReader(Console.OpenStandardInput());
 
    string[] input = reader.ReadLine().Split();
    int N = int.Parse(input[0]);
    int K = int.Parse(input[1]);
 
    int num = N;
    int count = 0; // 남은 물병의 개수파악
    int bottle = 0; // 구매한 꽃병의 수
 
    while (true)
    {
        while (num > 0)
        {
            if (num % 2 == 0)  // 짝수개이면 다 합칠 수 있고
            {
                num /= 2;
            }
            else // 아니라면 카운팅 하나 추가
            {
                num /= 2;
                count++;
            }
        }
 
        // 남은 물병의 개수가 K 개를 넘지 않으면 종료
        if (count <= K)
            break;
 
        // 아니라면 꽃병 하나 구매, N개수 증가
        bottle++;
        num = ++N;
        count = 0;
    }
 
    writer.WriteLine(bottle);
 
    writer.Close();
    reader.Close();
}

 

 

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