1094_막대기

사용 알고리즘: 구..현?

사용 언어: java

 

package week21;

import java.util.*;
import java.io.*;
public class Main_bj_1094_막대기 {
	static int[] powerOf2 = new int[7]; //2^6 = 64

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt(); //만들어야 하는 막대 길이
		
		int ans = 0;
		if(x > 64)
			System.out.println(-1);
		else {
			for(int i=6; i>=0; i--) {
				powerOf2[i] = (int) Math.pow(2, 6-i);
			}
			//System.out.println(Arrays.toString(powerOf2));
			
			int lastIdx = 6;
			while(x > 0) {
				while(true) {
					if(x >= (int) Math.pow(2, lastIdx) && powerOf2[lastIdx] > 0)
						break;
					lastIdx--;
				}
				
				x -= (int) Math.pow(2, lastIdx);
				ans++;
			}
			
			System.out.println(ans);
		}
	}

}

 

64 =>1개
32 32 =>2개
16 16 16 16 =>4개
8 8 => 8개
4 4 => 16개
2 2 => 32개
1 => 64개

7사이즈의 배열: 0~6인덱스

48 = 32 + 16
23 = 16 + 4+2 + 1

 

==> 이 문제를 읽어보면 결국, 64 이하의 수를 이진수를 표현해 나타내는 것이고, 이진수로 표현했을 떄 1의 개수를 구하는 것이다.