[백준 / BOJ] 1052 물병

문제

출처 : www.acmicpc.net/problem/1052

1052번: 물병

지민이는 N개의 물병을 갖고있다. 각 물병에는 물을 무한대로 부을 수 있는데, 처음에 모든 물병에는 물이 1리터씩있다. 지민이는 N개의 물병을 적절히 합쳐 K개이하의 물병으로 만들려하는데, 물병을 합칠때 는 다음 규칙에 따라 합칠수있다.

- 같은 물이 들어있는 물병만 합칠수있다.

이때, 물병을 더 이상 합칠수없다면, 1리터의 물이 들어있는 물병을 추가할수있다. K개 이하의 물병을 만들기위해 추가해야할 최소한의 물병의 개수를 출력하는 문제다.

 

풀이

시뮬레이션으로 풀리는 문제다.

처음에는 2차원 queue를 선언해서 물병을 하나하나 합쳐서 다음 idx로 넘겨주는 방식으로 구현했는데, 시간초과를 맞았다. 따라서 합치는 과정을 하나하나 합치는게아닌 한번에 해줘야한다. 

xL를 담고있는 물병의 갯수를 표현하는 1차원 배열을 만들어준다.

ex)

arr[1] = 3 // 1리터의 물을 담고있는 물병의 갯수가 3개

이때, 물병의 합치는 연산과, 남은 물병 계산은 나누기와 나머지연산으로 가능한데, 

같은 L의 물병의 /2 만큼 합쳐서 다음 L로 넘겨줄수있으므로,

1. 합치는 연산 = arr[L+1] += arr[L]/2;

이때, 합치고 남은 물병은 /2로 나누고 남은 나머지 이므로,

2. 남은 물병 계산 = arr[L] %= 2;

이 된다.

 

위 연산을 사용해서 구현하면되는데,

1. 합칠수있는 물병을 1L ~ NL 까지 전부 합쳐준다.

2. 이때, 남아있는 물병의 수가 K개 이하라면, 출력하고 종료한다.

3. 아니라면, 1L물병을 하나 늘려주고 다시 1번으로 돌아간다.

 

위 과정을 남아있는 물병의 수가 K개 이하일때까지 반복하면 답이다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1052%20%EB%AC%BC%EB%B3%91/main.cpp

devxb/JJUNalgo