백준 25943 - 양팔 저울(백준 - 그리디)

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

25943번: 양팔저울

 

* 문제 요약

1 부터 n 까지 번호가 매겨진 n 개의 자갈이 있다. 이 자갈들을 다음 절차에 따라 양팔 저울에 올려놓는다.

1. 1번 자갈을 왼쪽, 2번 자갈을 오른쪽에 올려 놓는다.

2. i = 3, ... n 번 자갈 각각에 대해서 차례로 다음 과정 중 하나를 수행한다.

  - A. 만약 양팔 저울이 평형을 이루는 경우, i 번 자갈을 왼쪽에 올려 놓는다.

  - B. 먄약 양팔 저울이 평형을 이루지 않는 경우, i 번 자갈을 가벼운 쪽에 올려 놓는다.

 

모든 자갈을 위의 규칙에 따라 올려 놓은 후에도 양팔저울은 평형을 이루지 않을 수 있다.

이 경우 가벼운 쪽에 무게추를 올려서 균형을 맞추려고 한다. 무게추는  1g, 2g, 5g, 10g, 20g, 50g, 100g 7종류가 있고, 무게추의 갯수에는 제한이 없다.

입력받은 자갈을 위 규칙에 따라 양팔저울에 올렸을 때, 최종적으로 평형을 맞추는데 추가적으로 필요한 무게추의 최소 갯수를 구하는 프로그램을 작성하시오.

 

* 입력

첫번째 줄에 자갈 갯수를 나타내는 양의 정수 n (2 <= n <= 10,000) 이 주어진다.

다음 줄에 n 개의 수들이 주어지는데, 이들은 번호 순서대로 자갈의 무게이다.

자갈의 무게는 각각 1 이상이며, 모든 자갈의 무게의 총합은 10,000,000 이하이다.

 

* 출력

최종적으로 평형을 맞추는데 추가적으로 필요한 무게추의 최소 갯수를 한 줄에 출력한다.

 

* 예시

 

* 해결 과정

필요한 무게추의 갯수를 최소화 하려면 왼쪽, 오른쪽 사이의 무게 차이를 초과하지 않는 선에서 가장 무거운 무게추부터 먼저 달아줘야 하므로 일단 각 무게추의 무게를 내림차순 형태로 정렬된 배열을 하나 만들고 시작한다.

 

각 자갈들을 위의 문제에서 제시한 규칙에 맞게 왼쪽, 오른쪽 각각에 적재할 때마다 각각의 무게를 계산해둔다.

자갈들을 모두 올려놓은 다음 수평이 맞지 않을 경우 무게추 배열에서 무게가 왼쪽, 오른쪽간의 무게 차이보다 작거나 같은 무게추 중 가장 큰 값을 찾아서 왼쪽, 오른쪽간 무게차이가 해당 무게추의 무게보다 작아지기 전까지 계속 해당 무게추를 올려주면서 사용된 무게추의 갯수 변수인 result 의 값을 1씩 증가시킨다.

 

반복문이 끝난 이후 왼쪽, 오른쪽간의 무게차이가 0 이 된 경우. 즉, 양팔저울이 수평이 된 경우 result 를 출력시켜 준다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int result = 0;
        int count = Integer.parseInt(br.readLine());
        int[] weight = { 100, 50, 20, 10, 5, 2, 1 };

        String[] input = br.readLine().split(" ");
        int left = Integer.parseInt(input[0]);
        int right = Integer.parseInt(input[1]);

        for (int i = 2; i < count; i++) {
            if (left == right) {
                left += Integer.parseInt(input[i]);
            } else {
                if (left < right) {
                    left += Integer.parseInt(input[i]);
                } else if (left > right) {
                    right += Integer.parseInt(input[i]);
                }
            }
        }

        if (left != right) {
            int sub = Math.abs(left - right);

            for (int i = 0; i < weight.length; i++) {
                if (sub >= weight[i]) {
                    while (sub >= weight[i]) {
                        sub -= weight[i];
                        result++;
                    }
                }

                if (sub == 0)
                    break;
            }
        }

        bw.write(result + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

왼쪽, 오른쪽간의 무게차이를 메우는데 사용할 무게추의 갯수를 최소화 하기 위해 무게차이보다 작거나 같은 무게를 가진 무게추들 중 가장 무거운 무게추를 활용하는 방식으로 매 단계마다 원하는 결과를 얻기 위한 최적의 로직을 수행하였으므로 그리디 알고리즘 문제에 해당된다.