[Algorithm/Java] 백준 1094번 - 막대기

---

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

---

🔍 문제 풀이

문제 도식화

💻 코드

전체 코드

그리디

현재 가지고 있는 가장 큰 막대기(64cm)부터 시작하여 목표 길이(X)를 만드는 데 필요한 만큼 사용

막대기 길이를 동적으로 절반씩 줄여가며 계산

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int x = Integer.parseInt(br.readLine());
        int stick = 64, cnt = 0;

        while(x != 0){
            if(stick > x) stick = stick / 2;
            else {
                x -= stick;
                cnt++;
            }
        }
        System.out.println(cnt);

    }
}

배열 사용

미리 배열에 저장해둔 막대기 길이들을 순서대로 확인

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int x = Integer.parseInt(br.readLine());

        int[] arr = {64, 32, 16, 8, 4, 2, 1};
        int idx = 0, cnt = 0;
        while(x > 0){
            if(x >= arr[idx]){
                cnt ++;
                x -= arr[idx];
            }else idx ++;
        }

        System.out.println(cnt);

    }
}