[BOJ-1094][비트마스킹] 막대기 -Java

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

1094번: 막대기

package algo;

import java.util.Scanner;

public class boj_1094_막대기 {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int length = sc.nextInt();
		int result=0;
		for(int i=0; i<7; i++) {
			if((length&(1<<i))>0) result++;
		}
		System.out.println(result);
	}
}

소요시간 : 15분

 

 

 

비트마스킹을 통해 입력으로 들어온 Xcm에서 1의 갯수를 뽑아주면 됩니다.

 

왜냐?

 

우선 지민이가 가지고 있는 막대기의 길이는 64cm입니다

 

그리고 문제에서 정확하게 반씩 자른다고 했습니다. 

 

그렇다면 지민이가 가지고 있을 수 있는 막대의 길이는

 

64, 32, 16, 8, 4, 2, 1 이렇게 7가지를 가질 수 있습니다.

 

곧 문제는 이 7가지의 막대중 몇가지를 사용해서 Xcm를 만들어라 하는 문제입니다.

 

예를 들어 입력으로 들어온 23을 보면

 

0 0 1 0 1 1 1 의 비트를 가지고 있습니다. 

 

즉, 1, 2, 4, 16 을 가진 막대기가 필요하다는 뜻입니다.

 

끝~