[백준 10312] Lodê (C#, C++) - soo:bak

문제 링크

10312번 - Lodê

설명

용량 k가 주어질 때, 각 차원의 아이템을 몇 개씩 담아야 가치의 합이 최대가 되는지 구하는 문제입니다.

차원이 클수록 무게 대비 가치 비율이 높으므로, 가장 큰 차원부터 최대한 담는 것이 최적입니다.

접근법

먼저 3의 거듭제곱을 용량 한도까지 미리 계산합니다.

이후 가장 큰 무게부터 담을 수 있는 개수를 구하고 남은 용량을 갱신합니다.

최상위 차원부터 0차원까지 개수를 출력합니다.

---

Code

C#

using System;
using System.Collections.Generic;

class Program {
  static void Main() {
    var t = int.Parse(Console.ReadLine()!);

    var weights = new List<int>();
    var cur = 1;
    while (cur <= 10_000_000) {
      weights.Add(cur);
      if (cur > 10_000_000 / 3) break;
      cur *= 3;
    }

    for (var tc = 0; tc < t; tc++) {
      var k = int.Parse(Console.ReadLine()!);

      var cnt = new int[weights.Count];
      for (var i = weights.Count - 1; i >= 0; i--) {
        cnt[i] = k / weights[i];
        k %= weights[i];
      }

      var top = weights.Count - 1;
      while (top >= 0 && cnt[top] == 0) top--;

      for (var i = top; i >= 0; i--) {
        Console.Write(cnt[i]);
        if (i > 0) Console.Write(' ');
      }
      Console.WriteLine();
    }
  }
}

C++

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

typedef vector<int> vi;

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

  vi w;
  int cur = 1;
  while (cur <= 10'000'000) {
    w.push_back(cur);
    if (cur > 10'000'000 / 3) break;
    cur *= 3;
  }

  int t; cin >> t;

  while (t--) {
    int k; cin >> k;

    vi cnt(w.size());
    for (int i = (int)w.size() - 1; i >= 0; i--) {
      cnt[i] = k / w[i];
      k %= w[i];
    }

    int top = (int)w.size() - 1;
    while (top >= 0 && cnt[top] == 0) top--;

    for (int i = top; i >= 0; i--) {
      cout << cnt[i];
      if (i) cout << ' ';
    }
    cout << "\n";
  }

  return 0;
}

```