[백준 알고리즘] 1094문제 (막대기)

[백준 알고리즘]

백준 알고리즘에 막대기 문제도 쉬울 거라 생각했어요ㅠ 근데....

문제를 읽으면 읽을 수록 도저히 이해가 되질 않아서 한참을 봤어요 .

진짜 오래봤습니다.

70% 나 맞췄는데 나는 왜 못 푸는 건지... 한참을 고민하고 또 고민했어요ㅠ

그래서 여기 저기 찾아보고 힌트보고 해서 결국엔 이해를 했어요

ex) x = 23 일 때 

1. 막대기를 반으로 나눈다 64 -> 32 / 32

2. 둘 중에 하나를 일단 제외해 두고 짧은 것이 x 보다 크기 때문에 32 막대기 하나는 버린다.

3. 남은 32 막대기를 다시 나눈다 32 -> 16 / 16

4. 다시 하나를 제외하고 x와 비교 하니 x 보다 작다 즉, x를 만들 재료 하나를 찾은 것임

5. 나머지 16을 버리지 않고 다시 반으로 나눈다 16 -> 8 / 8

6. 4에서 찾은 x의 재료 16과 지금 8을 더하면 x 보다 크기 때문에 8 하나를 다시 버린다.

7. 나머지 8을 다시 반으로 나눈다 8 -> 4 / 4

8. 이제는 x의 재료 16과 4를 더하게 되면 20이므로 x 보다 작다 그러므로 또 다른 x의 재료를 찾음

9. 이런 식으로 계속 x의 값과 똑같이 나올 때까지 찾는 것이다.

문제부터 이해하시면 금방 풀릴 문제이니 

문제 이해에 도움이 되게 예시로 몇자 적어놨어요

도움이 되길 바래요

import java.util.Scanner;
 
public class Beak1094 {
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        int length = 64;
        int x = sc.nextInt();
        int count = 0;
        int sum = 0;
 
        while (x > 0) {
 
            if (length > x) {
                length /= 2;
            } else {
                count++;
                x -= length;
            }
        }
        System.out.println(count);
    }
}