BOJ_1094 : 막대기

👉 문제링크

1094번: 막대기

---

---

🔸 문제 분석 🔸

• 64cm 막대기를 원하는 크기(x)의 막대기로 만들때, 조각의 개수를 출력한다.
  • 모든 막대의 합이 x보다 크면 다음 과정을 반복한다.
    • 가장 짧은 막대를 절반으로 자른다.
    • 자른 막대의 절반을 버렸을때도 전체 합이 x보다 크다면, 그 막대를 버린다.
• 막대 조각의 개수는 과정의 반복 횟수와 같다.

🔸 코드 🔸

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> arr = new ArrayList<Integer>();
        arr.add(64);

        int x = sc.nextInt();
        int sum = 64;

        while(sum > x){
            int min = 65, idx = 0;
            for (int i = 0; i < arr.size(); i++){
                if (arr.get(i) < min){
                    min = arr.get(i);
                    idx = i;
                }
            }
            int temp = arr.get(idx)/2;
            arr.set(idx, temp);
            arr.add(temp);

            if (sum-arr.get(idx) >= x){
                arr.remove(arr.size()-1);
                sum -= temp;
            }
        }
        System.out.println(arr.size());
    }
}

🔸 코드 해석 🔸

• ArrayList에 막대들을 넣어서 계산한다.
  • 처음은 64cm 막대가 있고 총합 sum도 64이다.
  • 문제조건대로 sum > x 이면 과정을 반복한다.
    • 최소값과 그 인덱스를 찾는다.
    • 최소값을 절반 자른다.
      • arr.set()으로 최소값 인덱스의 값을 그 절반으로 수정한다.
      • arr.add()로 최소값의 절반을 추가한다.
    • 만약 sum에서 최소값의 절반을 빼더라도 x보다 크다면, 최소값의 절반을 ArrayList와 sum에서 뺀다.
• 반복이 끝나면 ArrayList의 원소의 개수를 출력한다.

---

🔸 end 🔸

• 생각보다 헷깔리는 부분이 많았던 문제였지만, 풀고나니 그렇게 어렵지는 않은 것 같다.
• 다른 풀이를 보니 개선할 점이 많았다.
  • 최소값이 항상 마지막 인덱스로 오므로, 최소값찾기 반복문을 할 필요가 없었다.
  • 막대기의 수는 과정의 반복횟수로 알 수 있으므로 ArrayList도 사용할 필요가 없었다.
  • 태그를 보니 비트마스킹으로도 풀 수 있는 것 같다.
• 아래는 다른 답지, 위는 필자의 풀이 결과이다.