📌 문제
하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다.
무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오.
예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다.
✔ 접근방법
누적합을 이용하는 아이디어까지 생각을 했는데.. 그 다음단계가 생각이 나지 않아서.. 생각보다 고민을 많이 했다. 약간 낫놓고 기역자 모르는 꼴..
생각해줘야하는 부분은 배열이 오름차순으로 정렬되어있을 때,
누적합의 숫자까지 만들 수 있다는 것이다.
숫자를 만들 수 없는 경우는 현재까지의 누적합 + 1 보다 다음 인덱스의 입력값이 큰 경우를 의미한다.
즉, 누적합[i] + 1 < input[i+1] 인 경우가 있으면 누적합[i]+1의 값을 출력하고 없는 경우엔 모든 값을 다 더한 누적값 + 1을 출력하면 된다.
또한, 제일 작은 값이 1이 아닌 경우엔 무조건 1을 출력하도록 한다.
✔ 코드
import java.util.Arrays;
import java.util.Scanner;
//저울
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] input = new int[n];
int answer = 0;
for (int i = 0; i < n; i++) {
input[i] = sc.nextInt();
}
// 오름차순으로 정렬
Arrays.sort(input);
// 제일 작은 추의 값이 1이 아닌경우
if (input[0] != 1) {
System.out.println(1);
return;
}
// 누적합을 담는 변수
int sum = input[0];
for (int i = 1; i < n; i++) {
if (sum + 1 < input[i]) {
answer = sum + 1;
break;
}
sum += input[i];
}
//모든 저울을 더 한 값까지 만들 수 있는 경우
if (answer == 0)
answer = sum + 1;
System.out.println(answer);
}
}
아자 (*•̀ᴗ•́*)و