[백준] | JAVA, 자바 | 1094번 - 막대기

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

1094번: 막대기

---

문제 요약 :

아래와 같은 과정을 거쳐서 막대를 자르려고 한다.

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

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

 

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

---

문제 풀이 :

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

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());

        ArrayList<Integer> stick = new ArrayList<>();
        stick.add(64);

        while (true) {
            int sum = 0;
            for (int i = 0; i < stick.size(); i++) {
                sum += stick.get(i);
            }
            if (sum == x) {
                System.out.println(stick.size());
                break;
            } else if (sum > x) {
                int shortStick = stick.get(stick.size() - 1);
                stick.remove(stick.size() - 1);
                int half = shortStick / 2;
                stick.add(half);
                if (sum - half >= x) continue;
            } else {
                stick.add(stick.get(stick.size() - 1) / 2);
            }
        }
    }
}

 

1. x 입력받기

2. 막대의 길이를 저장할 ArrayList 생성, 64 추가

3. while문 반복

4. 막대의 길이의 합을 저장할 변수 sum 생성

5. stick에 저장된 막대의 길이들을 합하여 sum에 저장

6. sum이 x와 같다면 stick 길이를 출력하고 종료

6 - 1. sum이 x보다 크다면 가지고 있는 막대 중 길이가 가장 짧은 것을 가져와 shortStick에 저장하고 그 값을 제거

6 - 2. 가장 짧은 막대를 절반으로 자르고 stick에 추가, 만약 sum - half가 x보다 크거나 같다면 계속 진행

6 - 3. sum이 x보다 작다면 가장 짧은 막대를 절반으로 자르고 stick에 추가