[백준] C++ 1052(물병)

 

#include <iostream>

using namespace std;

int arr[1001];

int main(void)
{
	int a=0;
	int size=0;
	
	cin>>a>>size;
	
	for(int i=0; i<size; i++)
	{
		arr[i]=1;
	}
	
	a=a-size;
	
	if(a<size)
	{
		cout<<0;
		return 0;
	}
	
	int circle=0;
	
	while(true)
	{
		if(a==0)
		{
			break;
		}
		if(a-arr[circle]>=0)
		{
			a=a-arr[circle];
			arr[circle]=arr[circle]*2;
		}
		else
		{
			if(circle==size-1)
			{
				a=(-(a-arr[circle]));
				break;
			}
			circle=(circle+1)%size;
		}
		
	}
	
	cout<<a;
	
	return 0;
}

 

상점에서 사야 하는 물병의 최솟값을 구하는 문제이다.

 

어떻게 하면 물병의 최솟값을 구할 수 있을까??

1.먼저 지민이가 한 번에 K개의 물병을 옮길 수 있다.

2.물병은 2^n승 리터로 채워져있다.

 

예를 들어 입력으로 13개의 물병과 지민이가 5개의 물병을 옮길 수 있다고 주어진다고 생각해 보자.

먼저 물병 5개를 그린다.

여기서 한번 고민을 해봐야 한다. 어떻게 하면 물병을 가장 적게 살까??

순서대로 2의 n승만큼 채우면 어떻게 될까??

 

이렇게 채우게 되면 2번째 물통에 1만큼 부족해서 하나의 물병만 상점에서 사야 한다.

그런데 이렇게 접근하는 방법이 올바른 방법인가??

 

물통의 크기에 제한이 없기 때문에 이렇게 접근하는 방법은 옳은 방법이 아니다.

그럼 어떻게 접근해야하는가??

가장 앞에 있는 물병에 채울 수 있을 채워준다(2^n승만큼)

이렇게 그림이 그려진다.

흐름을 한번 살펴보겠다.

첫 번째 물통에는 처음에 1만큼 채워져있었기 때문에 1이 필요하다.(1+1=2) 

이제 첫 번째 물통에는 2만큼 채워져있기 때문에 2가 필요하다(2+2=4)

마지막으로 첫 번째 물통에는 4만큼 채워져있기 때문에 4가 필요하다(4+4=8)

여기서 멈추는 이유는 다음까지 진행하면 (8+8이 되기 때문에 현재 가지고 있는 물병을 초과하기 때문이다.)

초과하지 않는 선에서 채울 수 있을 만큼 채우고 다음 물통으로 넘어간다. 이제 두 번째 물통을 보면 1만큼 채워져 있기 때문에 1이 필요하다.(1+1=2)

(8+2+1+1+1=13) 상점에서 물통을 사지 않고도 5개의 물병에 물을 채울 수 있다.

 

즉 낮은 인덱스의 물병부터 채울 수 있을 만큼 채우는 방법이 가장 적은 양의 물병을 살 수 있는 방법이다.

 

주의할 점

1.한 번에 옮길 수 있는 물병의 개수가 가지고 있는 물병의 개수보다 크다면??(N<K)

2.딱 나누어떨어진다면??

3.정답이 없는 경우가 존재하는가??

 

해결방법

1.옮길 수 있는 물병의 개수가 가지고 있는 물병의 개수보다 크다면 상점에서 물통을 살 필요가 없다.(크기가 1인 물통을 들고 가면 됨.)

2.break;

3.이 문제에서는 정답이 없는 경우는 존재하지 않는다. 무조건 정답이 존재하는 문제이다.