[백준 2437] 저울 (C#, C++) - soo:bak

문제 링크

2437번 - 저울

설명

양팔 저울에서 추들을 한쪽에만 올릴 수 있을 때, 주어진 추들로 만들 수 없는 양의 정수 무게 중 최솟값을 구하는 문제입니다.

접근법

추들을 무게 순으로 정렬한 뒤 앞에서부터 순서대로 확인합니다. 현재까지 확인한 추들로 1부터 어떤 값까지 연속으로 만들 수 있다면, 다음 추의 무게가 그 범위를 벗어나지 않아야 범위를 확장할 수 있습니다.

예를 들어 1부터 5까지 만들 수 있는 상태에서 다음 추가 6 이하라면 그 추를 더해 범위를 확장할 수 있습니다. 하지만 다음 추가 7 이상이라면 6을 만들 방법이 없으므로 6이 답이 됩니다.

누적 합을 0으로 시작해서 각 추를 확인하며, 추의 무게가 누적 합 + 1보다 크면 그 값이 만들 수 없는 최솟값입니다. 모든 추를 확인해도 끊기지 않으면 누적 합 + 1이 답입니다.

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var n = int.Parse(Console.ReadLine()!);
      var arr = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
      Array.Sort(arr);

      var sum = 0L;
      foreach (var w in arr) {
        if (w > sum + 1)
          break;
        sum += w;
      }
      Console.WriteLine(sum + 1);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vl;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  vl w(n);
  for (int i = 0; i < n; i++)
    cin >> w[i];
  sort(w.begin(), w.end());

  ll sum = 0;
  for (ll x : w) {
    if (x > sum + 1)
      break;
    sum += x;
  }
  cout << sum + 1 << "\n";

  return 0;
}