[백준] 1094번 - 막대기 [Java]

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

 

[백준] 1094번 - 막대기 [Java]

[백준] 1094번 - 막대기 [Java]

---

1.  아이디어

 

이 문제는 1부터 64 사이의 2의 제곱수로 X를 만드는 문제와 동일한 문제가 된다. 64부터 1까지 반복문을 통해 제곱수의 개수를 세는 방식으로 간단하게 해결할 수 있고 비트마스킹을 활용해 X를 2진수로 나타냈을 때 1의 개수를 세는 방식으로도 해결할 수 있다.

---

2. 문제풀이

 

기본 구현은 for문의 인덱스를 2로 나눠가며 1의 개수를 세도록 구현했고, 비트마스킹의 경우 bitCount 메서드로 1인 비트의 개수를 간단하게 셀 수 있다.

---

3. 코드

 

import java.io.*;

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

        int X = Integer.parseInt(br.readLine());

        int cnt = 0;
        for (int i = 64; i >= 1; i /= 2) {
            if (X >= i) {
                X -= i;
                cnt++;
            }
        }

        System.out.println(cnt);
    }
}

import java.io.*;

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

        int X = Integer.parseInt(br.readLine());

        System.out.println(Integer.bitCount(X));
    }
}

---

4. 후기

 

- for문

- 비트마스킹