[백준 14969] Taro’s Shopping (C#, C++) - soo:bak

문제 링크

14969번 - Taro’s Shopping

설명

서로 다른 두 물건의 가격 합이 m을 넘지 않도록 하면서 가능한 최대 합을 구하는 문제입니다.

접근법

가격을 정렬한 뒤, 투 포인터로 합을 조절하며 최대값을 갱신합니다.
조건을 만족하는 쌍이 없으면 NONE을 출력합니다.

---

Code

C#

using System;
using System.Linq;
using System.Text;

class Program {
  static void Main() {
    var parts = Console.In.ReadToEnd().Split();
    var idx = 0;
    var sb = new StringBuilder();

    while (true) {
      var n = int.Parse(parts[idx++]);
      var m = int.Parse(parts[idx++]);
      if (n == 0 && m == 0) break;

      var arr = new int[n];
      for (var i = 0; i < n; i++)
        arr[i] = int.Parse(parts[idx++]);
      Array.Sort(arr);

      var l = 0;
      var r = n - 1;
      var best = -1;
      while (l < r) {
        var sum = arr[l] + arr[r];
        if (sum > m) r--;
        else {
          if (sum > best) best = sum;
          l++;
        }
      }

      if (best == -1) sb.AppendLine("NONE");
      else sb.AppendLine(best.ToString());
    }

    Console.Write(sb);
  }
}

C++

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

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

  int n, m;
  while (cin >> n >> m) {
    if (n == 0 && m == 0) break;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
      cin >> a[i];
    sort(a.begin(), a.end());

    int l = 0, r = n - 1;
    int best = -1;
    while (l < r) {
      int sum = a[l] + a[r];
      if (sum > m) r--;
      else {
        if (sum > best) best = sum;
        l++;
      }
    }

    if (best == -1) cout << "NONE\n";
    else cout << best << "\n";
  }

  return 0;
}