[ 𝗕𝗢𝗝 ] 2437번 저울 - 그리디 | JavaScript

🎯 문제 설명

🧩 백준 2437번 - 저울 | 골드2

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다.

무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오.

예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다.

입력

• 첫째 줄: 1 ≤ 저울추의 개수 N ≤ 1,000
• 둘째 줄: N개의 저울 추의 무게
  • 1 ≤ 각 추의 무게 ≤ 1,000,000

7
3 1 6 2 7 30 1

출력

주어진 추들로 측정할 수 없는 양의 정수 무게 중 최소값을 출력한다.

21

👩🏻‍💻 문제 풀이

1. 문제를 단계적으로 나누기

한 번에 하나씩 추를 선택하면서 만들 수 있는 무게의 범위를 확장해 나가는 단계로 나눌 수 있습니다. 따라서 1부터 차례로 만들 수 있는 모든 무게를 최대한 만들어봅니다. 그러다 현재 추로 만들 수 없는 첫번째 무게가 나오면 그게 답이 됩니다.

1. 가장 좋은 것을 선택

가장 가벼운 추부터 하나씩 선택하는 게, 가장 좋은 선택입니다. 작은 무게부터 순서대로 측정 가능한 범위를 점점 넓혀나갈 수 있기 때문입니다.

따라서 우선 추를 오름차순으로 정렬해 줍니다.

const weights = [3, 1, 6, 2, 7, 30, 1].sort((a, b) => a - b);
// [1, 1, 2, 3, 6, 7, 30] 이렇게 정렬됩니다.

1. 선택을 확정하고 진행

만들 수 있는 최대 무게의 범위를 target 이라고 하면, 처음에는 1 부터 시작합니다. 즉, 현재까지 만들 수 있는 범위는 1 ~ (target - 1) 입니다.

현재 추		target	새 target
1	1 ≦ 1 (✅)	1	1 + 1 = 2
1	1 ≦ 2 (✅)	2	2 + 1 = 3
2	2 ≦ 3 (✅)	3	3 + 2 = 5
3	3 ≦ 5 (✅)	5	5 + 3 = 8
6	6 ≦ 8 (✅)	8	8 + 6 = 14
7	7 ≦ 14 (✅)	14	14 + 7 = 21

여기까지 했을 때, 1 부터 20까지 만들 수 있는 겁니다.

1. 반복 종료

어떤 추의 무게가 target보다 크면, 그 순간이 target 무게를 만들 수 없는 경우이고 답이 됩니다.

현재 추		target	새 target
30	30 > 21 (❌)	21	-

이를 코드로 구현합니다.

const target = 1; // 묙표 무게는 무조건 추의 누적 값보다 1씩 커지도록 1로 시작합니다.

// 추 배열을 순회하면서 target(추의 누적 값 + 1)을 만들 수 있는 지 비교합니다.
for(let i = 0; i < weights.length; i++) {
	if(weights[i] <= target) {
		// 현재 추의 무게가 target보다 작거나 같으면 만들 수 있는 무게입니다.
		// 현재 추를 사용해 만들 수 있는 무게를 늘려줍니다. (target에 현재 추 무게를 더합니다.)
		target += weights[i]
	} else {
		// 추의 무게가 target보다 크면, 해당 값을 만들 수 없으므로 target이 답이 되므로 순회를 멈춥니다.
		break;
	}
}

실제로 확인을 해보면 다음과 같이 20까지 만들 수 있고, 21을 만들 수 없습니다.

target : 1 = 1
target : 2 = 1 + 1
target : 3 = 1 + 2
target : 4 = 1 + 1 + 2
target : 5 = 2 + 3
target : 6 = 1 + 2 + 3
target : 7 = 1 + 1 + 2 + 3
target : 8 = 2 + 6
target : 9 = 3 + 6
target : 10 = 1 + 3 + 6

target : 11 = 1 + 1 + 3 + 6
target : 12 = 1 + 2 + 3 + 6
target : 13 = 1 + 2 + 3 + 7
target : 14 = 1 + 1 + 2 + 3 + 7
target : 15 = 2 + 6 + 7
target : 16 = 1 + 2 + 6 + 7
target : 17 = 1 + 1 + 2 + 6 + 7
target : 18 = 2 + 3 + 6 + 7
target : 19 = 1 + 2 + 3 + 6 + 7
target : 20 = 1 + 1 + 2 + 3 + 6 + 7
target : 21 = X

최종 코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const N = Number(input[0]);
const weights = input[1].split(' ').map(Number).sort((a, b) => a - b);

let target = 1;

for (let i = 0; i < N; i++) {
  if (weights[i] <= target) {
    target += weights[i];
  } else {
    break;
  }
}

console.log(target);