[BOJ] 1094 막대기 - Java

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

1094번: 막대기

 

---

1. 문제 요약

64cm 막대기를 Xcm로 만드려고 한다. 

1. 길이가 가장 짧은 막대기를 이등분했을 때, 이등분된 두 막대기 중 하나를 제외하고, 가지고 있는 모든 막대의 길이가

    X보다 크거나 같으면 제외한 걸 버린다.

    X보다 작으면 버리지 않는다.

2. 이 과정을 반복한다.

총 몇 개의 막대로 Xcm를 만들 수 있는지를 출력한다.

 

2. 풀이

두 가지 방법이 있다.1. 직접 수행하는 방법 - 작은 수부터 오름차순으로 정렬하는 우선순위 큐를 생성한다. - 64를 우선순위 큐에 넣고 시작한다. 하나씩 poll해서 이등분해봤을 때,    총 합이 X보다 크면 두 번 offer 해주고, 작으면 한 번 offer 해준다. - 총 합이 X와 같으면 끝나고, 이등분한 길이가 1보다 작으면 큐에서 poll()해주기만 하고 끝난다.

 

2. 이진수답은 X를 이진수로 만들었을 때 1의 개수와 같다.Integer.bitCount(X) 를 이용하면 한 줄로 끝난다.

Intger.bitCount( 수 ) => 수를 이진수로 만들었을 때 1의 개수를 출력한다.

3. 코드

1) 직접 수행

package a22_10_29;

import java.io.*;
import java.util.*;

public class 막대기 {

	static int X, ans;
	static PriorityQueue<Integer> pq;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc<=T; tc++ ) {
			X = Integer.parseInt(br.readLine());
			pq = new PriorityQueue<>( (o1, o2) -> o1-o2 ); //숫자 작은 순으로 정렬해야 함
			
			ans = 0;
			solution();
			System.out.println("#"+tc+" "+ans);
		}
	}
	
	static void solution() {
		pq.offer(64);
		if (X == 64) {
			ans = 1;
			return;
		}
		while (true) {
			int cur = pq.poll();
			if (cur/2 < 1) break;
			
			int sum = cur/2;
			for (int num : pq) {
				sum += num;
			}
			if (sum == X) {
				pq.offer(cur/2);
				break;
			} else if (sum > X) {
				pq.offer(cur/2);
			} else if (sum < X) {
				pq.offer(cur/2);
				pq.offer(cur/2);
			}
		}
		ans = pq.size();
	}
}

2) 이진수 풀이

import java.io.*;
import java.util.*;

public class 막대기 {

	static int X, ans;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc<=T; tc++ ) {
			X = Integer.parseInt(br.readLine());
			ans = Integer.bitCount(X);
			System.out.println("#"+tc+" "+ans);
		}
	}
}