저울들을 합쳐서 만들 수 없는 무게를 구하면 된다.
간단하게 풀 수 있는데 그냥 무게들을 정렬해 놓고 작은 것부터 더해 나가다가 다음 무게가 이전까지의 모든 무게의 합보다 커버리면 무게의 합+1부터는 만들 수 없다고 판단하면 된다.
좀 더 자세히 설명해보자면, 작은것부터 큰것까지 무게들을 정렬했을 때 1번째부터 n번째 무게까지의 합을 sum_n이라고 하자.
그리고 1,2,3,...., sum_n은 전부 다 만들 수 있다고 가정하자.
이 때 sum_n보다 n+1번째 무게가 작다면, sum_n과 n+1번째 무게의 합 즉, 1부터 sum_(n+1) 까지도 전부 다 만들 수 있다.
(1,2,3,..., sum_n을 만들 수 있다고 가정했기 때문에 n+1번째 무게에 1,2,..., sum_n을 더하면 되기 때문)
만약 sum_n보다 n+1번째 무게가 크다면, 어떤 수를 쓰더라도 sum_n + 1은 만들 수 없다.
(1번째부터 n번째까지 다 더한게 sum_n인데 n+1번째 무게가 그거보다 커버리면 당연히 만들 수 없다)
수학적 귀납법과 같은 구조인데 결과적으로 이런 논리로 만들 수 없는 최소 무게를 구할 수 있다.
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
int N;
ll arr[10004];
int main()
{
ll sum = 0;
scanf("%d",&N);
for(int i=1;i<=N;i++)
{
scanf("%lld",&arr[i]);
}
sort(arr+1,arr+N+1);
if(arr[1]!=1)
{
printf("1");
return 0;
}
for(int i=1;i<=N;i++)
{
if(i!=1 && sum+1 < arr[i]) break;
sum += arr[i];
}
printf("%lld",sum+1);
}해결 코드이다.
1번째 무게가 1이 아니면 1부터 만들 수가 없으니까 안된다는 것만 빼먹지 않으면 금방 풀 수 있는 문제였다.
