[백준] 1094 막대기 - Java

문제

https://www.acmicpc.net/problem/1094

 

---

 

문제 개요

이 문제는 주어진 막대의 길이를 절반으로 나누고 원하는 길이만큼 만들기 위해 최소한 몇 개의 막대를 사용하는지를 묻고 있습니다. 막대의 길이를 이진법으로 표현한 후, 이진수의 '1'의 개수를 세면, 원하는 길이를 만들기 위해 필요한 막대의 수를 알 수 있습니다.

접근 방법

1. 처음에 64cm 길이의 막대가 있고, 목표는 Xcm 길이의 막대를 만드는 것입니다.
2. 64는 이진법으로 표현하면 1000000이고, 막대를 절반으로 자를 때마다 이진법에서 '1'의 개수는 하나씩 줄어듭니다.
3. 이진법에서 '1'이 나오는 위치는 Xcm를 만들기 위해 필요한 막대 길이를 나타냅니다.
4. 따라서 X를 이진수로 표현했을 때, '1'의 개수만큼의 막대가 필요합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int ans = 0; // 필요한 막대 수
        int n = Integer.parseInt(br.readLine()); // 입력된 값 X
        String s = Integer.toBinaryString(n); // X를 이진수로 변환

        // 이진수에서 '1'의 개수를 세면 필요한 막대 수와 동일
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '1') ans++;
        }
        System.out.println(ans);
    }
}