[Java] 백준알고리즘 #1094 막대기

백준알고리즘 #1094 막대기 문제

 

막대의 길이를 절반으로 자른 뒤 원하는 수보다 작다면 하나를 버리고, 크다면 작은 것을 반으로 잘라서 원하는 n만큼의 막대를 만드는 문제이다.

 

 

먼저 필요한 변수부터 만들어보자

막대기의 개수를 확인해줄 count변수

막대기의 길이를 확인하는 stick 변수

잘라서 모은 막대기의 합을 확인할 sum 변수 이렇게 구성할 수 있겠다.

int n = sc.nextInt();
int count = 1;
int stick = 64;
int sum = stick;

sum을 stick으로 초기화 한 이유는 while문을 통해 보도록 하자.

조건을 반복해야 하므로 while문을 사용한다. 이 때의 조건은 sum != n 으로 하자.

while(sum != n) {
	stick = stick/2;
	if(sum > n) {
		sum = sum - stick;
	}
	else {
		sum += stick;
		count++;
	}
}

먼저 막대기를 반으로 자른 후 sum이 n보다 크다면 sum에 반으로 자른 막대기를 뺀다.

그러면 수가 64 32 16 등 차례대로 줄어들게 된다.

여기서 만약 입력한 값이 33 이라고 하면

else 문으로 들어가서 sum에 32+16(stick을 반으로 자른 값) 이 들어가고

다시 while문으로 돌아올 때는 다시 빼는 과정이 시작된다.

 

본 문제는 몇개의 막대기를 붙여야하는지를 요하는 문제이므로 count++를 if문이나 while문 안이 아닌 else안에 두어야 결과가 제대로 출력된다.

반으로 자른 막대기가 구하는 수보다 크다면 (sum > n) 하나를 버리게 되기 때문이다.

 

즉 차례로 반으로 자른 후, 버리고 남은 자투리를 더해줄 때에만 count를 증가하면 된다.

 

전체 코드를 보면 다음과 같다.

import java.util.Scanner;

public class Baek1094 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int count = 1;
		int stick = 64;
		int sum = stick;

		while (sum != n) {
			stick = stick / 2;
			if (sum > n) {
				sum = sum - stick;

			} else {
				sum += stick;
				count++;
			}

		}
		System.out.println(count);

		sc.close();

	}

}