https://www.acmicpc.net/problem/2885
문제
> 학교 근처 편의점에 새 초콜릿이 들어왔다.
> 이 초콜릿은 막대 모양이고, 각 막대는 정사각형 N개로 이루어져 있다.
> 초콜릿의 크기(정사각형의 개수)는 항상 2의 제곱 형태이다.
> 즉, 1, 2, 4, 8, 16, ...개의 정사각형으로 이루어져 있다.
> 상근이는 점심식사로 초콜릿을 먹는다.
> 이때, 적어도 K개 정사각형을 먹어야 남은 수업을 졸지 않고 버틸 수 있다.
> 상근이의 친구 선영이도 초콜릿을 좋아한다.
> 선영이는 초콜릿은 돈을 주고 사기 아깝다고 생각하기 때문에, 상근이가 주는 초콜릿만 먹는다.
> 상근이는 막대 초콜릿를 하나 산 다음에, 정확하게 K개 정사각형이 되도록 초콜릿을 쪼갠다.
> K개는 자신이 먹고 남는 것은 선영이에게 준다.
> 막대 초콜릿은 나누기 조금 어렵게 되어 있어서, 항상 가운데로만 쪼개진다.
> 즉, 정사각형이 D개 있는 막대는 D/2개 막대 두 조각으로 쪼개진다.
> K개 정사각형을 만들기 위해서, 최소 몇 번 초콜릿을 쪼개야 하는지와 사야하는 가장 작은 초콜릿의 크기를 구하는 프로그램을 작성하시오.
> 상근이는 초콜릿을 하나만 살 수 있다.
> 꼭 한 조각이 K개일 필요는 없고, 여러 조각에 있는 정사각형을 합쳤을 때 K개이면 된다.접근
문제에서 초콜릿의 조각 수가 2의 거듭제곱으로 나오기 때문에 이런 문제는 2진수로 따져 풀 수 있다.
따라서 K가 2의 거듭제곱이면 K조각짜리 한덩이 쓰면 끝나서 K, 0번 출력이고
거듭제곱이 아니라면 2진수로 바꿔서 K의 비트 길이에서 오른쪽에서 부터 1이나올 때까지의 수를 빼주면 총 잘라야하는 수가 된다.
문제해결
> K를 입력받고 구매할 가장 작은 초콜릿을 위해 Integer.githestOneBit로
K보다 작은 가장 큰 2의 거듭제곱을 저장한다.
> 이 수가 K와 같다면 해당 수인 choco와 0을 출력한다. 쪼개지 않아도 된다는 뜻이다.
> 이제 다르면 cnt에 K의 비트수 - 오른쪽에서 1이나올때까지의 0의 개수를 구한다.
> K의 비트수는 예를들어 9면 1001이라 4를 원하지만 컴퓨터는 그렇지않다.
> nuberOfLeadingZeros를 통해 왼쪽에서 1이 나올 때까지의 0의 개수를 센다.
> 즉 Integer이므로 총 32비트에서 1001이나올 때까지니까 28이된다.
> 이 값을 Integer.SIZE에서 빼면 4를 얻을 수 있다.
> 이 값에서 이제 오른쪽에서 1이 나올 때까지의 0의 수 numberOfTrailingZeros로 구해준다. 즉, 1001이면 0, 1100이면 2가 나온다.
> 예제의 6을 보면 110 -> 3이고 오른쪽에서 세면 1이므로 3-1로 2가 된다.
> 결과로 choco의 두배를 해준 값과, 위에서 얻어낸 결과를 출력한다.
> choco는 K보다 작은 2의 거듭제곱중 젤 큰값이므로 6이라면 4가 되므로 이 4를 얻기위해 8에서 시작해야한다. 따라서 2를 곱한다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
//2885번 초콜릿 식사
static int K;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
K = Integer.parseInt(br.readLine());
int choco = Integer.highestOneBit(K);
if(choco != K) {
int cnt = Integer.SIZE - Integer.numberOfLeadingZeros(K) - Integer.numberOfTrailingZeros(K);
System.out.println(choco * 2 + " " + cnt);
return;
}
System.out.println(choco + " " + 0);
}
}
후기
choco를 반복문으로 2를 곱해가면서 찾은 뒤, cnt도 K에서 choco를 뺴고, 2를 나누고, 빼고 나누고 를 반복하며 누적하면서 찾았었다.
하자만 예전에 막대나누기 문제에서 이런 문제는 2진법으로 비트에 접근하면 되는걸 알았기에 자바의 문법에서 비트를 통해 접근하는 방법을 써보았다.
