[백준] 알고리즘 분류(수학,JAVA)1094번, 막대기

문제 링크

1094번: 막대기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 막대기를 자르는 과정은 문제에서 자세히 설명하고 있습니다.

2. Xcm의 막대기를 만들 때 붙이는 막대기의 개수를 결과로 출력합니다.

3. 막대기의 초기 길이는 항상 64cm입니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. Xcm 막대기를 만들기 위해 자르고 붙이는 과정을 탐색합니다.

 

3. Xcm가 만들어질 때 붙이는 막대기의 개수를 결과로 출력합니다.

 

 

막대기 자르고 붙이는 과정.

 

막대기를 절반으로 자르고 1개를 버린다고 가정하였을 때

 

남은 막대기의 합이 X보다 같거나 크면 잘린 막대기 1개를 버립니다.

 

 

X = 31일 때

 

64 ÷ 2 = 32

 

32 32

 

31 ≤ 32 : True

 

막대기 버리고 다시 자르는 과정 진행!

 

 

막대기를 절반으로 자르고 1개를 버린다고 가정하였을 때

남은 막대기의 합이 X보다 작으면 잘린 막대기 1개를 버리지 않습니다.

 

X = 33일 때

 

64 ÷ 2 = 32

 

32 32

 

33 ＞ 32 : True

 

막대기를 버리지 않고 자르는 과정 다시 진행!

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

X : 23

 

2. Xcm 막대기를 만들기 위해 자르고 붙이는 과정을 탐색합니다.

 

초기 막대기 : 64cm

 

막대기 자르고 붙이는 과정 진행!

 

32 32

 

23 ≤ 32 : 잘린 1개의 막대기 버리기!

 

현재 막대기 : 32

 

 

16 16

 

23＞16 : 막대기 버리지 않기!

 

현재 막대기 : 16 16

 

 

8 8 16

 

23 ≤ 24 : 잘린 1개의 막대기 버리기!

 

현재 막대기 : 8 16

 

 

4 4 16

 

23 ＞ 20 : 막대기 버리지 않기!

 

현재 막대기 : 4 4 16

 

 

2 2 4 16

 

23 ＞ 22 : 막대기 버리지 않기!

 

현재 막대기 : 2 2 4 16

 

 

1 1 2 4 16

 

23 ≤ 23 : 잘린 1개의 막대기 버리기!

 

현재 막대기 : 1 2 4 16

 

 

3. Xcm가 만들어질 때 붙이는 막대기의 개수를 결과로 출력합니다.

 

23cm을 만들 때 사용하는 막대기 : 1 2 4 16

 

4을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• 막대기 자르고 붙이는 과정을 진행하여 Xcm의 막대기를 만드는 개수를 구합니다.
• Xcm을 만드는 막대기의 개수를  BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

결과코드

import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int X = Integer.parseInt(br.readLine());
        //length : 막대기 길이 합, cur : 가장 짧은 막대기 길이, answer : 막대기 개수
        int length = 64, cur = 64, answer = 1;
        //X가 64일 때
        if(X == 64)
            bw.write("1");	//초기 막대기만 사용!
        else{		//X != 64
            //막대기 자르고 붙이는 과정 진행!
            while(true){
                cur /= 2;	//막대기 절반으로 자르기
                length -= cur;	//절반으로 자른 1개 막대기 버렸다고 가정!
                if(length < X){	//막대기의 합 < X
                    answer++;	//막대기 버리지 않기
                    length += cur;
                }else if(length == X)	//막대기의 합 == X
                    break;
            }
            bw.write(answer + "");	//막대기의 개수 BufferedWriter 저장
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}