[백준, 1094번] 막대기 (수학, 비트 마스킹, Java)

문제설명

입력 & 출력

나의 풀이

이번 "백준 - 막대기" 문제는 주어진 수 X를 만들기 위한 최소 막대기 개수를 구하는 문제입니다. 이 문제에서 막대기는 처음에 64의 길이를 가지고 있으며, 길이가 반으로 자를 수 있습니다.

1. 64 길이의 막대기부터 시작하여, 필요한 만큼 X에 맞게 막대기를 사용합니다.
2. 매번 X와 stick(현재 막대기 길이)을 비교하여, stick이 X보다 크다면 그 막대기를 자르지 않고 반으로 줄여 나갑니다.
3. stick이 X보다 작거나 같을 때는 그 막대기를 사용하여 X를 차감합니다.
4. 이렇게 반복하여 X가 0이 될 때까지 막대기를 사용하고, 사용한 막대기의 개수를 출력합니다.

 

 

코드를 보기 쉽게 그림으로 표현하자면 위와 같습니다. 

• 초기 막대 길이 64 → 너무 커서 사용X → 32로 자름
• 32 → 여전히 큼 사용 X → 16으로 자름
• 16 → 23(X)보다 작으므로 사용 (23-16=7 남음)
• 8 → 7보다 크므로 사용X → 4로 자름
• 4 → 7보다 작으므로 사용 (7-4=3 남음)
• 2 → 3보다 작으므로 사용 (3-2=1 남음)
• 1 → 1과 같으므로 사용 (1-1=0)

 

따라서 입력(X) 가 23이라면 실제 사용된 막대는 4개입니다.

 

다른 풀이 (비트 마스크)

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

        while (X > 0){
            if(X % 2 == 1){
                cnt++;
            }
            X /= 2;
        }
        System.out.println(cnt);
    }
}

 

주어진 막대기들의 길이는 64, 32, 16, 8, 4, 2, 1 이렇게 이진수 자리값(2의 거듭제곱)을 따릅니다. 따라서, X를 만들기 위해서는 X를 이진수로 나타내었을 때, 1인 비트만큼 막대기를 사용하면 됩니다.

• X가 이진수로 표현되었을 때, 1인 비트가 있는 자리만큼 막대기를 사용하면 됩니다.
• 예를 들어, X = 23의 이진수 표현은 10111입니다. 여기서 1인 비트는 4개(64, 32, 16, 8)입니다. 따라서 최소 4개의 막대기를 사용해야 23을 만들 수 있습니다.

1.  X를 반으로 줄이는 과정

• X /= 2
• 이 연산은 사실 이진수로 한 비트를 오른쪽으로 이동하는 것과 동일한 효과를 가집니다.
• 즉, X의 가장 오른쪽 비트가 사라지고, 그 다음 비트가 가장 오른쪽으로 내려오는 것입니다.

2.  1의 개수를 세는 과정

• X % 2 == 1을 사용하여, X의 가장 오른쪽 비트가 1인지 0인지 판단합니다.
• X % 2 == 1이 true라면, X의 가장 오른쪽 비트는 1이므로, 이를 cnt에 카운트합니다.

이진수로 변환하지 않고도 나머지 연산(X % 2)과 정수 나누기 연산(X /= 2)을 사용하면, 각 비트가1인지0인지를 직접 확인할 수 있기 때문에 이진수 변환 없이도1의 개수를 셀 수 있습니다.

---

다른 풀이 2

위 풀이를 보면 결국 이진수의 1의 개수를 세는 것입니다. 따라서 , X를 이진수로 변환한 뒤에도 문제를 풀 수 있습니다.

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int X = sc.nextInt();
        
        // X를 이진수로 변환한 후 "1"의 개수를 세기
        String binaryString = Integer.toBinaryString(X);  // X를 이진수 문자열로 변환
        int cnt = binaryString.replaceAll("0", "").length();  // "0"을 모두 제거하고 "1"의 개수 세기
        
        System.out.println(cnt);
    }
}

 

toBinaryString()메서드를 사용하여 입력 X를 2진수 문자열로 만들어주고, replaceAll()메서드를 사용하여 0을 없애주어 전체길이를 출력한다면 1의 개수를 손 쉽게 구할 수 있습니다.