물병
출처 : 백준 #1052
| 시간 제한 | 메모리 제한 |
|---|---|
| 1초 | 512MB |
문제
지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번에 K개의 물병을 옮길 수 있다. 하지만, 지민이는 물을 낭비하기는 싫고, 이동을 한 번보다 많이 하기는 싫다. 따라서, 지민이는 물병의 물을 적절히 재분배해서, K개를 넘지 않는 비어있지 않은 물병을 만들려고 한다.
물은 다음과 같이 재분배 한다.
먼저 같은 양의 물이 들어있는 물병 두 개를 고른다. 그 다음에 한 개의 물병에 다른 한 쪽에 있는 물을 모두 붓는다. 이 방법을 필요한 만큼 계속 한다.
이런 제약 때문에, N개로 K개를 넘지않는 비어있지 않은 물병을 만드는 것이 불가능할 수도 있다. 다행히도, 새로운 물병을 살 수 있다. 상점에서 사는 물병은 물이 1리터 들어있다.
예를 들어, N=3이고, K=1일 때를 보면, 물병 3개로 1개를 만드는 것이 불가능하다. 한 병을 또다른 병에 부으면, 2리터가 들어있는 물병 하나와, 1리터가 들어있는 물병 하나가 남는다. 만약 상점에서 한 개의 물병을 산다면, 2리터가 들어있는 물병 두 개를 만들 수 있고, 마지막으로 4리터가 들어있는 물병 한 개를 만들 수 있다.
입력
첫째 줄에 N과 K가 주어진다. N은 107보다 작거나 같은 자연수이고, K는 1,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 상점에서 사야하는 물병의 최솟값을 출력한다. 만약 정답이 없을 경우에는 -1을 출력한다.
입출력 예시
예제 입력 1
3 1
예제 출력 1
1
예제 입력 2
13 2
예제 출력 2
3
예제 입력 3
1000000 5
예제 출력 3
15808
풀이
생각
먼저 같은 양의 물이 들어있는 물병 두 개를 고른다.라는 문구에 사로잡혀 이진수로 접근할 생각을 못하고 객체를 생성하여 Recursion을 이용하여 풀었다...(현타가 오네요..)- 풀이를 보면 너무너무 긴데, 간단하게 논리만 설명하도록 하겠다.
풀이 설명
- 우선
Case c객체는 물병의 개수(cnt), 개별 물병의 물 양(liter), 현재 보유한 물병 수(bottle), 관리해야하는 총 물의 양(totalWater)를 인스턴스 변수로 갖고, bucket이라는 ArrayList에 따로 보관할 물병들을 넣는다. - 현재 내가 가지고 있는 물병의 개수가 홀수개 일 때, +1 또는 -1을 할 수 있는데, +1은 새로운 물병이 추가되는 경우이고, -1은 현재의 물(liter)만큼을 보유한 물병 하나를 제외하는 것이다. 여기서 제외된 물병은 bucket에 담긴다.
- 꼭 모든 물병이 같은 양의 물을 담고 있어야 하는 것이 아니므로, bucket에 개별 물병들을 보관할 생각을 했다.
- 이 때문에 Recursion을 사용했고,, 너무나도 코드가 복잡해졌다 ㅠ
java code
// 백준 1052번 물병
package algorithm;
import java.util.*;
public class Baekjoon1052 {
private static ArrayList<Case> answer = new ArrayList<>();
private static int k; // 목표 도달 물병 수
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 물병의 수
k = sc.nextInt(); // 만들려고 하는 목표 물병의 수
int cnt = 0; // 새로 추가한 물병의 개수
int liter = 1; // 시작할 때 각 물병에 든 물의 양
Case c = new Case(n, cnt, liter, n);
cal(c);
int minAnswer = answer.get(0).cnt;
for (int i = 0; i < answer.size(); i++) {
// System.out.println(answer.get(i));
minAnswer = Math.min(minAnswer, answer.get(i).cnt);
}
System.out.println(minAnswer);
}
private static void cal(Case c) {
if(c.bottle < 1){
return;
}
if(c.liter < 1){
return;
}
// 따로 보관하는 물병이 없을 경우
if (c.bucket.size() == 0) {
if (c.bottle <= k) {
answer.add(c);
return;
}
}
// 따로 보관하는 물병이 있을 경우 (bottle의 개수와 bucket에 담긴 물병의 개수의 합)
if (c.bottle + c.bucket.size() <= k) {
int bucketSum = c.bucket.stream().mapToInt(Integer::intValue).sum();
if ((c.liter * c.bottle) + bucketSum == c.totalWater) {
answer.add(c);
return;
}
}
if (c.bottle % 2 != 0) {
Case plusCase = new Case(c.bottle + 1, c.cnt + c.liter, c.liter, c.totalWater + c.liter);
Case minusCase = new Case(c.bottle - 1, c.cnt, c.liter, c.totalWater);
for(int i: c.bucket){
plusCase.bucket.add(i);
minusCase.bucket.add(i);
}
minusCase.bucket.add(c.liter);
cal(plusCase); // recursion
cal(minusCase); // recursion
} else {
c.liter *= 2; // 물병 합치기(물의 양 증가)
c.bottle /= 2; // 물병 합치기(물병의 양 감소)
cal(c);
}
}
}
class Case {
int cnt; // 새로 추가한 물병의 개수
int liter; // 현재 보유하고 있는 물병의 개별 물 양
int bottle; // 현재 보유한 물병의 수
int totalWater; // 객체가 가진 총 물의 양
ArrayList<Integer> bucket = new ArrayList<>(); // 따로 보관할 물병
Case(int bottle, int cnt, int liter, int totalWater) {
this.bottle = bottle;
this.cnt = cnt;
this.liter = liter;
this.totalWater = totalWater;
}
public String toString() {
return "cnt:" + cnt + ", liter:" + liter + ", bottle:" + bottle + ", totalWater:" + totalWater + ">>>>" + bucket;
}
}
개선된 javacode(1) 설명
-
이진수로 바꿔 생각하기
먼저 같은 양의 물이 들어있는 물병 두 개를 고른다.라는 문구에서 알 수 있듯, 2의 제곱수로 물병을 합쳐 표현할 수 있게 된다. (이 부분을 생각 못했음)
-
예시에서 N = 13이고, K = 2일 때를 생각해보자.
- N =
1101 - 이 때 N에서 1의 개수는 곧 만들 수 있는 물병을 뜻한다.
- 따라서 1의 개수가 현재 3개이기 때문에 K개보다 작거나 같게 만들어주어야 한다.
- 1씩 더하면서 1의 개수를 체크하고, K개보다 작거나 같아지면 계산을 멈추도록 하여보자.
1101+0001=1110
1110+0001=1111
1111+0001=10000
- 총 3번을 더했을 때 2진수 중 1의 개수가 K개보다 같거나 작아졌다.
- 따라서 3번(각 1 리터) 물을 추가해주면 된다.
- N =
-
풀이를 처음 보고 정말 기발하다고 생각했다. 보통 알고리즘 문제를 풀 때 비트마스킹 기법을 고려해 본적이 없었는데 이번 기회를 통해 생각의 틀을 넓히는 계기를 가져보았다.
개선된 java code(1)
// 백준 1052번 물병 개선된 풀이(1)
package algorithm;
import java.util.*;
import cs01.Adder;
import cs01.Convertor;
public class Baekjoon1052U {
private static int answer = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n, k;
n = sc.nextInt();
k = sc.nextInt();
Convertor convertor = new Convertor();
Adder adder = new Adder();
boolean[] binaryN = convertor.dec2bin(n);
final boolean[] ONE = convertor.dec2bin(1);
while(!(bitCount(binaryN, k))){
binaryN = adder.byteadder(binaryN, ONE);
answer += 1;
}
System.out.println(answer);
}
private static boolean bitCount(boolean[] binaryArr, int k) {
int count = 0;
for(int i = 0; i < binaryArr.length; i++){
if (binaryArr[i] == true){
count++;
}
}
if (count <= k){
return true;
}
return false;
}
}- 이전에 구현했던 byteadder(2진수 합 메서드)와 dec2bin(십진수 -> 2진수 변환 메서드)를 이용하였다.
bitCount라는 메서드를 만들어 1의 개수를 카운트하고, K개보다 작거나 같으면 return 하도록 하였다.
개선된 javacode(2) 설명
count변수가 K개보다 작아질 때까지 1씩 더하면서 2로 나눈다.
개선된 java code(2)
// 백준 1052번 물병 개선된 풀이(2)
package algorithm;
import java.util.*;
public class Baekjoon1052U2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n, k;
n = sc.nextInt();
k = sc.nextInt();
int answer = 0;
while(true){
int count = 0;
int bottles = n;
while(bottles != 0){ // 물을 최대한 나눠가질 수 있을만큼 나누기
if (bottles % 2 == 1){
count++;
}
bottles = bottles / 2;
}
if(count <= k){
break;
}
answer++;
n++;
}
System.out.println(answer);
}
}
나는 날마다 모든 면에서 점점 더 나아지고 있다.