2437번: 저울

2022.01.23

 

문제 출처:

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

 

문제 분석:

입력받은 무게의 추들로 만들 수 없는 최소 양의정수 구하기

 

문제 해결:

 

"N의 무게를 만들 수 있을때 N + arr[i] 이하는 모두 만들 수 있다."

 

N의 무게를 만들 수 있다 : 0~N까지 추로 만들 수 있다.

arr[i] ~ arr[i] + N 이 가능하다 이기때문에 위의 식이 성립한다.

 

즉,  N  >= a[i] 일때 N + arr[i] 까지 모두 만들 수 있다.

 

 

내 소스코드:

using namespace std;

const int INF = 987654321;

int main()
{
   int N;
   int arr[1002];

   scanf("%d", &N);

   for (int i = 0; i < N; i++)
   {
      scanf("%d", &arr[i]);
   }

   sort(arr, arr + N);

   int ans = 1;

   for (int i = 0; i < N; i++)
   {
      if (arr[i] <= ans)
         ans += arr[i];
      else
         break;
   }

   printf("%d", ans);

   return 0;
}

 

고찰:

고민 많이 해봤지만 못풀어서 해설을 봤다. 그리디로 풀리는 문제라는게 놀라울 따름이다.