백준1094_막대기

문제

지민이는 길이가 64cm인 막대를 가지고 있다. 어느날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대를 만드려고 한다.

막대를 자르는 가장 쉬운 방법은 절반으로 자르는 것이다. 지민이는 아래와 같은 과정을 거쳐서 막대를 자르려고 한다.

1. 지민이가 가지고 있는 막대의 길이를 모두 더한다. 처음에는 64cm 막대 하나만 가지고 있다. 이 때, 합이 X보다 크다면, 아래와 같은 과정을 반복한다.
   1. 가지고 있는 막대 중 길이가 가장 짧은 것을 절반으로 자른다.
   2. 만약, 위에서 자른 막대의 절반 중 하나를 버리고 남아있는 막대의 길이의 합이 X보다 크거나 같다면, 위에서 자른 막대의 절반 중 하나를 버린다.
2. 이제, 남아있는 모든 막대를 풀로 붙여서 Xcm를 만든다.

X가 주어졌을 때, 위의 과정을 거친다면, 몇 개의 막대를 풀로 붙여서 Xcm를 만들 수 있는지 구하는 프로그램을 작성하시오. 

입력

첫째 줄에 X가 주어진다. X는 64보다 작거나 같은 자연수이다.

출력

문제의 과정을 거친다면, 몇 개의 막대를 풀로 붙여서 Xcm를 만들 수 있는지 출력한다.

예제 입력

23

예제 출력

4

예제 입력 2

32

예제 출력 2

1

[코드]

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 막대기 cm
        System.out.println(makeStick(N));
    }
 
    public static int makeStick(int n) {
        int stick = 64;
        int count = 0;
        while (true) {
            if (stick > n) { // 반으로 갈랐을 때 n 보다 크다면 반 나누고 반 버리는 작업을 계속함
                stick = stick / 2;
            } else if (stick < n) { // 반으로 나눈 스틱이 n 보다 작으면 이제 다르게 작업해줘야함 
                count++; // 스틱 하나는 일단 써야하니까 count 늘리기
                int stick_O = stick; // 현재 가지고 있는 스틱을 저장하기 위한 변수. 일단은 반절로 시작!
                int stick_D = stick; // 나머지 반은 계속 쪼개기
 
                while (stick_O != n) { // 현재 가지고 있는 막대기 합이 n이랑 같지 않다면
                    stick_D = stick_D / 2; // 나머지 반 자르기
                    if (stick_O + stick_D <= n) {  
                        stick_O += stick_D;
                        count++;
                    }
                }
 
                break;
            } else {
                count++;
                break;
            }
        }
        return count;
    }
}
 

[알고리즘]

뭐라고 설명해야할진 모르겠지만... 우선 문제에서 말하는 대로 그대로 짰다. 만약, 23을 구하고자 하면

1. 64 길이의 막대가 16 16 까지 나눠질 때 까지는, 계속 반 나누고 반을 버려야 한다. (필요없으니까...)

2. 그 후부터는 16cm 막대는 보관해두고, 나머지 16cm 막대를 쪼개서 계속 숫자를 만들어 나가야한다.

3. 16cm를 반으로 쪼개 8cm * 2 개로 만든다. 16cm 막대 + 나눈 8cm 막대를 더하면 역시나 아직 23보다는 크기 때문에, 8cm 한개는 버리고 나머지 한개를 더 나눠야한다.

4. 한번 더 쪼갠 4cm 막대 + 현재 가지고있는 16cm 를 더하면 23보다 작으니까 보관한다.

5. 23이 될때까지 계속 막대를 쪼개고 쪼개서 원하는길이가 만들어지면 출력한다!

결국 문제에서 말하는거랑 똑같이 짠건데, 정리하자면 이렇다.

1. 반으로 나눈 막대 길이가 n 보다 작아질때까지 우선 반을 버리는 작업을 계속 해주고 (17,18줄)

2. 반으로 나눈 막대길이가 n보다 작을때부터는 쪼개고 보관하는 걸 반복해 원하는 숫자 만들기

3. 반으로 나눈 막대길이가 n 과 같을때는 막대 하나로 만들수 있는 것이므로 (64, 32, 16, 8, 4, 2, 1 과 같은 경우) 1개 출력!