[백준 1094번] 막대기 (Java 풀이)

백준알고리즘 1094번 : 막대기

 

문제의 설명은 굉장히 복잡한 듯 싶지만,

사실은 64 이하의 숫자를 2진수로 만들었을때, 1의 숫자를 구하는 것과 같다.

왜냐하면 똑같은 길이의 막대가 2개가 쓰일일이 없고,

우리는 막대를 계속 쪼개서 1까지 만들 수 있기 때문이다.

 

숫자를 2진수로 변환한 뒤, 1의 갯수를 세는 방식도 있지만,

나는 주어진 숫자를 받고 64에서 2씩 나누면서 주어진 숫자보다 더 작은 값이나오면

주어진 숫자를 차감시키는 방식으로 접근했다.

 

 

풀이 과정

---

1. 만들고자 하는 stick의 길이 X를 받는다. 
2. stick의 초기 길이(64)에서 반씩 나누어주면서, 길이 X보다 더 작은 값이 나오면
   X 값을 해당 숫자만큼 차감시키고, 차감 횟수를 센다.
3. X 값이 0이 나올때까지 진행한 뒤, 차감 횟수를 출력한다.

 

 

 

소스 ▽

import java.util.Scanner;

public class Main {// 1094번 막대기
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int leng = sc.nextInt();
		int stick = 64;

		int ans = 0;
		while (stick > 0) {
			if (stick <= leng) {
				leng -= stick;
				ans++;
			}
			if (leng == 0) {
				break;
			}
			stick /= 2;
		}
		System.out.println(ans);

	}

}