[Baekjoon 25943] 양팔저울 - JAVA

[Silver IV] 양팔저울 - 25943

문제 링크

성능 요약

메모리: 15232 KB, 시간: 156 ms

분류

그리디 알고리즘, 구현

문제 설명

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

1.  $1$번 자갈을 왼쪽, $2$번 자갈을 오른쪽에 올려놓는다.
2. $i = 3, \dots , n$번 자갈 각각에 대해서 차례로 다음 과정 중 하나를 수행한다.
   1. 만약 양팔저울이 평형을 이루는 경우, $i$번 자갈을 왼쪽에 올려 놓는다.
   2. 만약 양팔저울이 평형을 이루지 않는 경우, $i$번 자갈을 가벼운 쪽에 올려 놓는다.

모든 자갈을 위의 규칙에 따라 올려 놓은 후에도 양팔저울은 평형을 이루지 않을 수 있다. 이경우 가벼운 쪽에 무게추를 올려서 균형을 맞추려고 한다. 무게추는 1g, 2g, 5g, 10g, 20g, 50g, 100g 7종류가 있고, 무게추의 개수에는 제한이 없다.

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

입력

입력은 표준입력을 사용한다. 첫 번째 줄에 자갈 개수를 나타내는 양의 정수 $n$ ($2 ≤ n ≤ 10\,000$)이 주어진다. 다음 줄에 $n$ 개의 수들이 주어지는데, 이들은 번호 순서대로 자갈의 무게이다. 자갈의 무게는 각각 $1$이상이며, 모든 자갈의 무게의 총합은 $10\,000\,000$이하이다.

출력

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

문제 풀이

첫 번째 자갈은 왼쪽, 두 번째 자갈은 오른쪽에 둔다.

$i = 3$부터 $n$까지 반복하면서 각 자갈의 무게를 더해준다.

양팔저울이 평형이 아닌 경우, 무게가 더 가벼운 쪽에 무게추를 추가한다.

무게추의 추가 평형이 아니면, 무게추가 몇개인지 계산한다.

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

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

        int[] Weight = {100, 50, 20, 10, 5, 2, 1};
        int N = Integer.parseInt(br.readLine());
        StringTokenizer tokenizer = new StringTokenizer(br.readLine());

        int left = 0, right = 0;
        for (int i = 0; i < N; i++) {
            int P = Integer.parseInt(tokenizer.nextToken());
            if (left <= right) {
                left += P;
            } else {
                right += P;
            }
        }

        int diff = Math.abs(left - right);
        int cnt = 0;
        for (int i : Weight) {
            cnt += diff / i;
            diff %= i;
        }

        System.out.println(cnt);
        br.close();
    }
}

코드 풀이

int[] Weight = {100, 50, 20, 10, 5, 2, 1};
int N = Integer.parseInt(br.readLine());
StringTokenizer tokenizer = new StringTokenizer(br.readLine());

int left = 0, right = 0;
for (int i = 0; i < N; i++) {
    int P = Integer.parseInt(tokenizer.nextToken());
    if (left <= right) {
        left += P;
    } else {
        right += P;
    }
}

• Weight: 무게추의 무게를 나타내는 배열
• N: 자갈의 개수를 입력받을 변수
• 'P': N번만큼 자갈의 무게를 입력받을 변수
• 좌,우 무게를 비교해서 가벼운쪽에 자갈의 무게를 더해준다.

int diff = Math.abs(left - right);
int cnt = 0;
for (int i : Weight) {
    cnt += diff / i;
    diff %= i;
}

• Math 함수에 abs를 사용해서 어디가 더 무게가 무겁든 양수값이 나온다.
• cnt: 무게추의 추가 횟수를 저장할 변수
• 루프를 사용해 Weight배열을 순회하면서 무게 차이 diff를 해당 무게추로 나눈 몫을 cnt에 더하고, 나머지를 diff에 할당한다.

System.out.println(cnt);
br.close();

• cnt를 출력한다.