[Java/자바][백준] 1094번: 막대기

 

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

1094번: 막대기

 

---

 

✔️ 막대기 길이을 반으로 나누면서 '반으로 나눈 값을 더한 값'이 X 값이 될때까지 반복하기

 

🔹 막대기의 길이를 반으로 자른 값이 X값보다 작으면 나오면 보관하고, 크면 한 번 더 나눈다. 

🔹 이 과정을 반복하면서 보관하고 있는 막대기의 길이 합이 X값과 똑같아지면 반복을 멈추고, 막대기 개수를 출력한다.  

 

 

별거 아닌 반복인데 문제에서 말을 너무 헷갈리게 써놔서 잘 인지가 안된다. 그래서 그림을 그려가며 이해했다.

결국, 반으로 계속 나눈 값들을 만들어 가면서 그 값들의 합으로 X값을 만들어 내는 문제이다. 

 

 

 

 

 

 

☑️ [풀이]

import java.util.Scanner;

public class Q1094 {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		
		int X = sc.nextInt();
		//원래 들고 있는 막대기 길이
		int makdae = 64;
		
		//기존의 막대기에서 남은 길이 + 보관하고 있는 막대기 길이
		int hap = 0;
		
		//보관하고 있는 막대기 길이
		int keep = 0;
		
		//총 막대기 갯수
		int cnt = 1;
		
		while(true) {
			 if(makdae == X) {
				 break;
			 }
			 if(makdae!=X) {
				 //가지고 있는 막대를 절반으로 자른다 
				 makdae = makdae/2; 
				 
				 //위에서 자른 막대의 절반 중 하나를 버리고 남아있는 막대의 길이 + 보관하고 있는 막대기 길이
				 hap = makdae + keep;
				 
				 if(hap==X) {
					 break;
				 }
				 else if(hap>X){
					 //자른 막대의 절반 중 하나를 버리기
					 makdae = makdae;
				 }
				 else {
					 //hap이 X보다 작으면 해당 막대기 길이값을 누적하여 보관
					 keep += makdae;
					 
					 //기존 막대기 수 + 보관하는 막대기 개수 1 추가 
					 cnt++;				
				 }
			 }
		}
		System.out.println(cnt);
	}
}