[java] 백준 알고리즘 1094번 막대기 풀이

반으로 쪼개가면서 계속해서 더하면 되는 문제다.

예제 입력 1의 경우인 23cm은

23cm은 64cm보다 작기 때문에 반으로 쪼갠다. 그럼 32cm, 32cm가 나오는데 

32cm보다 23cm가 작기 때문에 32cm 나뭇가지 하나는 버리고 나머지 하나는 반으로 쪼갠다. 

그럼 16cm, 16cm가 나온다.

16보단 23이 크기 때문에 16cm 하나는 가지고 있고, 하나는 반으로 쪼갠다. (16cm 하나 킵한다)

8cm, 8cm가 되는데 (가지고 있던 16cm) 나뭇가지에 8cm를 더하면 24cm이므로 다시 8cm 나뭇가지 하나를 쪼개고, 

다른 8cm는 버린다.

4cm, 4cm가 나오는데, 가지고 있던 16cm 나뭇가지와 4cm 나뭇가지를 더하면 20cm! 그럼 이것도 킵한다.

남은 4cm를 다시 반으로 쪼갠다. 그럼 2cm, 2cm

붙인 나뭇가지 20cm에 2cm를 더하면 22cm! 

다른 2cm를 다시 쪼개면 1cm, 1cm. 이렇게 해서 22cm에 1cm를 더하고 다른 1cm는 버리면

23cm가 완성된다.

이제까지 사용한 나뭇가지는 결과적으로 16cm, 4cm, 2cm, 1cm로 총 4개의 나뭇가지를 사용했다.

코드로 구현하면 아래 소스를 참고하면 된다~!

* 풀이 소스

 
public class Baekjoon1094 {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int input = Integer.parseInt(br.readLine());
         int splitedBranch = 32; // 반으로 쪼갠 나뭇가지 길이 
         int dynamicCompare = 0; // 원하는 값과 입력된 값이 같아 지는 지 비교를 위한 값  
        int branchCount = 0; // 나뭇가지 
        
        if(input==64){
            branchCount = 1;
        }else{
            
            while(true){
                
                if(input == dynamicCompare+splitedBranch){ 
                    branchCount++;
                    break;
                }else if(input > dynamicCompare+splitedBranch){ // 쪼개진 나뭇가지를 붙여나감 
                    dynamicCompare += splitedBranch;
                    branchCount++; // 쪼개서 더해지므로 나뭇가지가 
                    splitedBranch = splitedBranch/2;
                }else if(input < dynamicCompare+splitedBranch){ // 입력된 값을 넘어버리기 때문에 나뭇가지를 다시 쪼갬 
                    splitedBranch = splitedBranch/2;
                }
            }
        }
        
        bw.write(String.valueOf(branchCount));
        bw.flush();
    }    
}