[백준 1789] 수들의 합 (C#, C++) - soo:bak

문제 링크

1789번 - 수들의 합

설명

서로 다른 N개의 자연수를 골라 그 합이 S가 되도록 하는 상황에서, S (1 ≤ S ≤ 4,294,967,295)가 주어질 때, 가능한 N의 최댓값을 구하는 문제입니다.

예를 들어, S = 20이라면 1 + 2 + 3 + 4 + 10 = 20 (N=5) 또는 1 + 2 + 17 = 20 (N=3) 등 여러 방법이 있지만, 이 중 N이 최대가 되는 경우를 찾아야 합니다.

접근법

N을 최대화하려면 가능한 한 작은 수들을 많이 사용해야 합니다.

가장 작은 자연수들은 1, 2, 3, 4, …이므로 이들을 순서대로 사용하는 것이 최적입니다.

1부터 k까지의 합은 k(k+1)/2입니다.

1 + 2 + 3 + … + k ≤ S를 만족하는 최대 k를 찾으면, k개의 서로 다른 자연수를 사용하여 S 이하의 합을 만들 수 있습니다.

만약 1부터 k까지의 합이 S보다 작다면, 나머지를 k번째 수에 더해주면 됩니다.

예를 들어, S = 20일 때:

• 1 + 2 + 3 + 4 + 5 = 15 (부족)
• 15에 5를 더하면 20인데, 5번째 수를 5 대신 10으로 바꾸면 됨
• 결과: 1 + 2 + 3 + 4 + 10 = 20 (N=5개)

다른 예로, S = 200일 때:

• 1 + 2 + … + 19 = 190 (부족)
• 1 + 2 + … + 20 = 210 (초과)
• 19개를 사용하되 마지막 수를 조정: 1 + 2 + … + 18 + 29 = 200 (N=19개)

구현 시에는 1부터 순차적으로 더해가면서 합이 S를 초과하는 순간의 직전 개수를 구하면 됩니다.

S가 최대 약 43억이지만, 1부터 k까지의 합은 k²에 비례하므로 k는 약 √(2S) ≈ 92,000 정도로 충분히 작아 시간 내에 계산할 수 있습니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var s = long.Parse(Console.ReadLine()!);
      long sum = 0, count = 0, current = 1;
      
      while (true) {
        sum += current;
        if (sum > s) break;
        count++;
        current++;
      }
      
      Console.WriteLine(count);
    }
  }
}

C++

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

typedef long long ll;

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

  ll s; cin >> s;
  ll sum = 0, count = 0, current = 1;
  
  while (true) {
    sum += current;
    if (sum > s) break;
    count++;
    current++;
  }
  
  cout << count << '\n';
  return 0;
}