JAVA/알고리즘

백준 1094 막대기 문제

위들 wedul 2018. 10. 3. 23:49
반응형

문제 내용
https://www.acmicpc.net/problem/1094

소스코드

자세한 소스는 참고 
https://github.com/weduls/algorithm/tree/master/%EC%8B%9C%EB%AE%AC%EB%A0%88%EC%9D%B4%EC%85%98/%EB%A7%89%EB%8C%80%EA%B8%B0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import java.util.Scanner;
import java.util.Stack;
import java.util.stream.IntStream;
 
public class Main {
 
    private static final double initLength = 64;
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        double goalLength = sc.nextDouble();
 
        calcFindLengthCount(goalLength);
    }
 
    /**
     * 구하고자 하는 막대 값을 받고 구하는 함수
     * 
     * @param goalLength
     */
    private static void calcFindLengthCount(double goalLength) {
        Stack<Double> staffs = new Stack<>();
        staffs.push(initLength);
 
        while (!isEqaulGoalLength(staffs, goalLength)) {
            double minStaff = staffs.pop() / 2;
 
            if (minStaff < 0) {
              System.out.print("fail.");
              return;
            }
 
            staffs.push(minStaff);
            if (calStaffsLength(staffs) < goalLength) {
                staffs.push(minStaff);
            }
 
            if (isEqaulGoalLength(staffs, goalLength)) {
                break;
            }
        }
 
        System.out.print(staffs.size());
    }
 
    /**
     * 현재 막대 길의의 합이 목표의 합과 일치한지 확인
     * 
     * @param staffs
     * @param goalLength
     * @return
     */
    private static boolean isEqaulGoalLength(Stack<Double> staffs, double goalLength) {
        return calStaffsLength(staffs) == goalLength;
    }
 
    /**
     * 현재 막대의 합을 구하는 메서드
     * 
     * @param staffs
     * @return
     */
    private static double calStaffsLength(Stack<Double> staffs) {
        return staffs.stream().reduce(0.0, Double::sum);
    }
}
 
cs


막대기가 원하는 길이가 될때까지 진행하면서 자른 막대기를 Stack에 집어 넣고 원하는 길이가 되면 stack에 쌓인 막대기의 개수를 화면에 보여 준다.



728x90
반응형