[BOJ] 1094번 막대기

개요

비트마스킹을 이용해 풀 수 있는 문제

문제링크

코드

import java.io.*;

public class Baekjoon1094{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int x = Integer.parseInt(br.readLine());

        int result = 64;    //막대의 총 길이
        int shortest = 64;  //가장 짧은 막대 길이
        int count = 1;      //막대의 갯수

        while(result > x) {
            shortest >>= 1;
            if(result-shortest >= x)
                result -= shortest;
            else
                count++;
        }
        bw.write(count+"\n");
        bw.flush();
    }
}

해결 과정

막대기의 길이가 64이므로 비트연산자를 이용해 1씩 이동하면 절반씩 줄여나갈 수 있다. 문제에서 주어진 알고리즘을 토대로 비트연산을 하면 쉽게 구할 수 있는 문제였다.

결과