[백준] 1094번 : 막대기

1094번: 막대기

---

[비트마스킹]

정수형 배열을 하나 준비한다. 사이즈는 대충 16이상이면 된다.

배열의 0 번째 원소에 1 << 6(64)를 넣어준다.

이제 인덱스를 1로 올려주고 while을 돌며 문제의 로직을 수행한다.

 

idx 미만의 루프를 돌며 배열 원소들의 합을 구한다.

그 합이 x와 같다면 그 때의 count를 result에 저장한다.

 

for루프를 빠져나와 idx를 증가시키고,

만약 sum > x라면 idx를 감소시킨다.

 

이제 비트 연산자를 이용해

            arr[idx] = (arr[idx-1] >> 1);
            arr[idx-1] = (arr[idx-1] >> 1);

idx번 째와 idx-1번째 원소를 idx-1번째에 있는 원소를 반으로 나눈 값으로 설정한다.

sum == x일 때 까지 반복

# Code </>

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 x = Integer.parseInt(br.readLine());

        int[] arr = new int[1 << 4];
        arr[0] = 1 << 6;

        int idx = 1, result = -1;
        while(true){
            boolean flag = false;

            int sum = 0, cnt = 0;
            for(int i=0; i<idx; i++){
                sum += arr[i];
                cnt++;
                if(sum == x){
                    result = cnt;
                    flag = true;
                }
            }
            if(flag) break;

            idx++;

            if(sum > x)
                idx--;

            arr[idx] = (arr[idx-1] >> 1);
            arr[idx-1] = (arr[idx-1] >> 1);
        }
        System.out.println(result);
    }
}