[백준 4864] Gold Coins (C#, C++) - soo:bak

문제 링크

4864번 - Gold Coins

설명

1일차에 1개, 다음 2일간 2개씩, 다음 3일간 3개씩… 식으로 k일 동안 k개를 지급하는 패턴이 반복됩니다. 시작일부터 주어진 일수까지 총 몇 개의 금화를 받는지 구하는 문제입니다.

입력은 여러 개의 일수가 주어지며, 0이 나오면 종료합니다.

접근법

1일부터 최대 일수까지 누적 합을 미리 계산해 둡니다. 지급 개수가 1개부터 시작해서, 해당 개수만큼 날이 지나면 다음 개수로 넘어가는 패턴을 시뮬레이션합니다.

각 질의에 대해 미리 계산된 누적 값을 바로 출력합니다.

---

Code

C#

using System;
using System.Text;

class Program {
  static void Main() {
    const int MAX = 10000;
    var pref = new int[MAX + 1];
    var day = 1;
    var val = 1;
    var sum = 0;

    while (day <= MAX) {
      for (var i = 0; i < val && day <= MAX; i++) {
        sum += val;
        pref[day] = sum;
        day++;
      }
      val++;
    }

    var parts = Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries);
    var sb = new StringBuilder();
    foreach (var p in parts) {
      var n = int.Parse(p);
      if (n == 0) break;
      sb.AppendLine($"{n} {pref[n]}");
    }

    Console.Write(sb);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;

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

  const int MAX = 10000;
  vi pref(MAX + 1, 0);
  int day = 1, val = 1, sum = 0;
  while (day <= MAX) {
    for (int i = 0; i < val && day <= MAX; i++) {
      sum += val;
      pref[day] = sum;
      day++;
    }
    val++;
  }

  int n;
  while (cin >> n && n)
    cout << n << " " << pref[n] << "\n";

  return 0;
}