👨💻 문제
✍️ 풀이
🤔 생각
물병은 같은 양의 물을 가진 물병 2개만을 합칠 수 있다.
1, 2, 4, 8, 16, ... 과 같은 2^n형태의 용량을 가질 수 있게 된다.
이는 2진수로 1, 10, 100, ...과 같은 형태이다.
즉 목표 물병의 수가 1개라면,
10000... 1로 시작하고 0개 이상의 0으로 이루어진 2진수 중 가장 작은 수를 만들면 된다.
그럼 1보다 많다면 어떻게 해야 할까?
예를 들어 목표 물병의 수가 3개라면,
10000, 100, 1
이런 식으로 3개의 10... 형태의 2진수를 만들 수 있도록 하면 된다.
해당 2진수들을 모두 합치면 10101이 되고,
1이 3개 포함된 2진수가 된다.
그렇다면 현재 물병의 수를 2진수로 표현한 후,
목표 물병의 수만큼의 1이 포함된 가장 작은 2진수를 만든다면 될 것이라는 생각이 든다.
1, 1, 1
하지만 위와 같이 3개의 2진수를 만든다면,
그 합은 11이 된다.
즉, 10은 1개도 될 수 있고 2개도 될 수 있다.
100은 4개까지도 될 수 있다.
111의 경우,
100, 10, 1 : 3개,
100, 1, 1, 1 : 4개,
10, 10, 1, 1, 1 : 5개,
10, 1, 1, 1, 1, 1 : 6개,
1, 1, 1, 1, 1, 1, 1 : 7개,
7개까지 쪼개질 수 있다.
여기서 111은 10진수로 7이다.
최대 해당 10진수만큼 쪼갤 수 있다.
하지만 2개는 될 수 없다.
2진수에 포함된 1의 개수 이하의 물병은 만들 수 없는 것이다.
그렇다면 이러한 성질을 이용하여 문제 해결 방법을 찾는다.
- n은 최대 n개까지 쪼갤 수 있다.
- 2진수에 포함된 1의 개수 이하의 물병은 만들 수 없다.
-
만약
현재 물병의 수가목표 물병의 수보다 작거나 같다면,0출력 후 종료 -
만약
현재 물병의 수가목표 물병의 수보다 많다면,-
해당 2진수가
목표 물병의 수보다 적은 수의1을 가졌더라도 필요한 만큼 쪼갤 수 있다.
0출력 후 종료 -
해당 2진수가
목표 물병의 수보다 많은 수의1을 가지고 있다면,
1의 개수가목표 물병의 수와 같거나 작을 때까지 값을 증가시킨다.
K = 2, 1011 --> 1100
K = 2, 1101 --> 1110 --> 10000
-
if (N <= K) {
System.out.println(0);
return;
}
...
if (countOne(binaryValue) <= K) {
System.out.println(0);
return;
}
subtractOne();
System.out.println(getDiff());2️⃣ 2진수
Java에는 Integer.toBinaryString()이라는 메소드가 존재한다.
해당 메소드는 숫자를 간단히 2진수를 표현한 문자열로 바꿔준다.
2진수의 자릿수를 변환해주어야 하기 때문에 해당 문자열을 배열로 변환하였다.
1100을 10000으로 만들어야 하는 경우, 배열의 크기가 변할 수 있다.
이러한 경우를 대비하기 위해 배열로 변환할 때 해당 문자열의 크기를 기준으로 하지 않고, 고정된 값을 기준으로 두었다.
N의 최댓값인 10000000을 2진수로 표현하여도 30자리를 넘지 않는다.
private static final int LENGTH = 30;
private static int[] binaryValue = new int[LENGTH];그렇기 때문에 2진수를 저장할 배열의 크기를 30으로 지정하였다.
1이 너무 많을 경우, 1을 줄여야 한다.
낮은 자리부터 해당 자리의 수가 1이라면 1을 더해 더 높은 자리로 올려버린다.
이를 반복하면 1의 수를 점차 줄일 수 있다.
올림수를 활용하였을 때, 2가 생겼다면, 1의 개수가 하나 줄어든 것이다.
101 -> 110 -> 200 -> 1000
private static void subtractOne() {
int oneCnt = countOne(binaryValue);
int i = LENGTH - 1;
while (oneCnt > K) {
if (binaryValue[i] == 1) {
binaryValue[i] = 0;
binaryValue[i-1]++;
for (int j=i-1; binaryValue[j] == 2; j--) {
binaryValue[j] = 0;
binaryValue[j-1]++;
oneCnt--;
}
}
i--;
}
}📄 전체 소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.stream.Collectors;
public class _1052 {
private static final int LENGTH = 30;
private static int N, K;
private static int[] binaryValue = new int[LENGTH];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
if (N <= K) {
System.out.println(0);
return;
}
String binaryN = Integer.toBinaryString(N);
Arrays.fill(binaryValue, 0);
int binaryNLength = binaryN.length();
for (int i=0; i<binaryNLength; i++) {
binaryValue[LENGTH - binaryNLength + i] = binaryN.charAt(i) - '0';
}
if (countOne(binaryValue) <= K) {
System.out.println(0);
return;
}
// System.out.println(Arrays.stream(binaryValue).mapToObj(String::valueOf).collect(Collectors.joining()));
subtractOne();
// System.out.println(Arrays.stream(binaryValue).mapToObj(String::valueOf).collect(Collectors.joining()));
System.out.println(getDiff());
}
private static int countOne(int[] binaryValue) {
int result = 0;
for (int value : binaryValue) {
result += value;
}
return result;
}
private static void subtractOne() {
int oneCnt = countOne(binaryValue);
int i = LENGTH - 1;
while (oneCnt > K) {
// System.out.println(Arrays.stream(binaryValue).mapToObj(String::valueOf).collect(Collectors.joining()) + ", " + oneCnt);
if (binaryValue[i] == 1) {
binaryValue[i] = 0;
binaryValue[i-1]++;
for (int j=i-1; binaryValue[j] == 2; j--) {
binaryValue[j] = 0;
binaryValue[j-1]++;
oneCnt--;
}
}
i--;
}
}
private static int getDiff() {
StringBuilder sb = new StringBuilder();
for (int e : binaryValue) {
sb.append(e);
}
return Integer.parseInt(sb.toString(), 2) - N;
}
}
