[백준] 1094. 막대기

문제 링크

[백준] 1094. 막대기

풀이 과정

문제에서 명시된 막대기를 자르는 과정은 해당 숫자를 2진수로 변환하는 과정입니다. 문제의 입력 예시 23으로 아래에서 설명하겠습니다.

초기에 64cm 막대는 1번 과정을 통해 위와 같이 잘립니다. 절반으로 잘린 오른쪽 32cm 막대를 버렸을 때, 남은 왼쪽 막대 길이(= 오른쪽 막대와 같음)는 X인 23cm보다 크므로 버립니다.

남은 32cm 막대를 다시 반으로 자릅니다. 잘린 하나의 막대는 16cm로 X인 23cm보다 작으므로 버리지 않습니다.

가지고 있는 막대 중 하나를 반으로 자릅니다. 잘린 하나의 막대를 제외한 나머지의 막대들의 길이 합은 16 + 8 = 24cm이고, X인 23cm보다 크므로 버립니다.

가지고 있는 막대 중 가장 짧은 막대를 반으로 자릅니다. 잘린 하나의 막대를 제외한 나머지 막대들의 길이 합은 16 + 4 = 20cm이고, X인 23cm보다 작으므로 버리지 않습니다.

가지고 있는 막대 중 가장 짧은 막대를 반으로 자릅니다. 잘린 하나의 막대를 제외한 나머지 막대들의 길이 합은 16 + 4 + 2 = 22cm이고, X인 23cm보다 작으므로 버리지 않습니다.

가지고 있는 막대 중 가장 짧은 막대를 반으로 자릅니다. 잘린 하나의 막대를 제외한 나머지 막대들의 길이 합은 16 + 4 + 2 + 1 = 23cm이고, X인 23cm과 같으므로 버립니다.

남은 막대들의 합이 X와 같아지므로 남은 막대의 개수 4가 정답이 됩니다. 막대는 최종적으로 16 + 4 + 2 + 1 의 형태로 잘리며, 이 형태는 10111(2) 의 이진수 표현과 같습니다. 따라서, 이 문제는 10진수 정수 X를 2진수 형태로 변환한 뒤, 1의 개수를 세어 출력하면 됩니다.

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String X = Integer.toBinaryString(sc.nextInt());
        int answer = 0;

        for (int i = 0; i < X.length(); i++) if (X.charAt(i) == '1') answer++;

        System.out.println(answer);
    }
}