[백준 23972] 악마의 제안 (C#, C++) - soo:bak

문제 링크

23972번 - 악마의 제안

설명

초기 금액 X원과 악마의 조건이 주어지는 상황에서, K (1 ≤ K ≤ 2×10⁸)와 N (1 ≤ N ≤ 2×10⁸)이 주어질 때, 손해를 보지 않는 최소 금액을 구하는 문제입니다.

악마의 제안은 다음과 같습니다. K원을 지불하면 남은 금액 (X - K)를 N배로 만들어줍니다. 손해를 보지 않으려면 최종 금액 N × (X - K)가 초기 금액 X 이상이어야 합니다.

부등식 N × (X - K) ≥ X를 정리하면 NX - NK ≥ X, 즉 (N - 1)X ≥ NK가 됩니다. 따라서 X ≥ NK / (N - 1)입니다.

N = 1인 경우, N - 1 = 0이 되어 나눗셈이 불가능하므로 어떤 금액으로도 손해를 피할 수 없습니다. 이때는 -1을 출력합니다. N > 1인 경우, X의 최솟값은 NK / (N - 1)을 올림한 값입니다.

접근법

먼저 N = 1인 특수 경우를 처리하고, 그 외의 경우 부등식을 풀어 최소 금액을 계산합니다.

N = 1이면 어떤 금액으로도 손해를 피할 수 없으므로 -1을 출력합니다.

이후, N > 1인 경우 X ≥ NK / (N - 1)을 만족하는 최소 정수를 구합니다. 이는 NK / (N - 1)의 올림값입니다. 정수 나눗셈에서 올림을 구하려면 나머지가 0이 아닐 때 몫에 1을 더합니다.

오버플로를 방지하기 위해 64비트 정수(long, long long)를 사용합니다. NK의 최댓값은 약 4×10¹⁶이므로 64비트로 충분합니다.

예를 들어, K = 100, N = 3인 경우:

X ≥ 3 × 100 / (3 - 1) = 300 / 2 = 150입니다. 나머지가 0이므로 정확히 150이 답입니다.

반면 K = 100, N = 4인 경우, X ≥ 4 × 100 / (4 - 1) = 400 / 3 = 133.333…이므로 올림하여 134가 답입니다.

N = 1, K = 100인 경우는 -1을 출력합니다.

단순 계산과 조건 분기만으로 해결되므로 시간 복잡도는 O(1)입니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var parts = Console.ReadLine()!.Split();
      var k = long.Parse(parts[0]);
      var n = long.Parse(parts[1]);

      if (n == 1) {
        Console.WriteLine(-1);
        return;
      }

      var num = n * k;
      var den = n - 1;
      var ans = num / den;
      if (num % den != 0)
        ans++;

      Console.WriteLine(ans);
    }
  }
}

C++

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

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

  ll k, n; cin >> k >> n;
  if (n == 1) {
    cout << -1 << "\n";
    return 0;
  }

  ll num = n * k;
  ll den = n - 1;
  ll ans = num / den;
  if (num % den != 0)
    ans++;

  cout << ans << "\n";

  return 0;
}