백준 1094 막대기(구현, 비트마스킹)

1094번: 막대기

매우 간단한 문제이지만 배울점이 많았던 문제다

가지고 있는 막대를 반으로 계속 나누면서 남은 애들이랑 이어붙여서 요구하는 막대의 길이를 구하는건데 

 

1. 문제에 나와있는대로 그대로 구현하기

1. 가지고 있는 막대를 이등분 한다
2. 이등분한 막대 중 하나를 빼고 나머지 stack에 있는 애들을 모두 더한다
3. if sum >= X : 이등분한거 버린다(아무것도 안한다)
    if sum < X : 버리지 않는다(다시 stack에 넣는다)

package pratice;

import java.util.Scanner;
import java.util.Stack;

public class algo1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for (int tc = 1; tc < T+1; tc++) {
           int X = sc.nextInt();

            Stack<Integer> stack = new Stack<>();
            stack.push(64);

            if (X == 64)
                System.out.println("#"+tc+" "+1);
            else{
                while(true){
                    int temp = stack.pop();
                    temp /= 2;
                    stack.add(temp);

                    int sum = 0;
                    for (int i = 0; i < stack.size(); i++) {
                        sum += stack.get(i);
                    }

                    if (sum == X)
                        break;

                    else if(sum < X){
                        stack.add(temp);
                    }
                }

                System.out.println("#"+tc+" "+stack.size());



            }


        }


    }
}

 

2. 비트마스킹

X = 63 이라면, 
64 -> 32 32(안버림) -> 32 16 16(안버림) -> 32 16 8 8(안버림) -> 32 16 8 4 4(안버림) -> 32 16 8 4 2 2(안버림) -> 32 16 8 4 2 1 1(버림)
[32 16 8 4 2 1] 막대를 이어야함

X = 6이라면,
64 -> 32 32(버림) -> 16 16(버림) -> 8 8(버림) -> 4 4(안버림) -> 4 2 2(버림)
[4 2] 막대를 이어야함

X = 13이라면,
64 -> 32 32(버림) -> 16 16(버림) -> 8 8(안버림) ->8 4 4(안버림) -> 8 4 2 2(버림) -> 8 4 1 1(버림)
[8 4 1] 막대를 이어야함

이거 잘 봤을 때 비트연산으로 생각해보면
X를 2진수로 바꿨을 때 막대를 이어야하는 부분은 1인 부분임

따라서! X를 2진수로 표시한다음에 1의 개수를 센다

package pratice;

import java.util.Scanner;

public class algo1_1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for (int tc = 1; tc < T+1; tc++) {
            int X = sc.nextInt();
            System.out.println(Integer.toBinaryString(X).replace("0","").length());

        }
    }
}