[백준 2291] Sequence (C#, C++) - soo:bak

문제 링크

2291번 - Sequence

설명

길이가 N이고 합이 M인 비감소 자연수 수열 중에서 사전순으로 K번째 수열을 출력하는 문제입니다.

접근법

특정 조건을 만족하는 수열의 개수를 세는 함수가 필요합니다. 현재 위치에서 now 이상의 값으로 시작하고, 길이가 d이며, 합이 sum인 비감소 수열의 개수를 동적 프로그래밍으로 계산합니다.

다음으로 수열의 첫 번째 원소를 결정합니다. 첫 번째 원소가 1일 때의 경우의 수가 K 이상이면 1을 선택하고, 그렇지 않으면 K에서 해당 경우의 수를 빼고 다음 값으로 넘어갑니다.

이후 같은 방식으로 두 번째, 세 번째 원소를 차례대로 결정합니다. 각 위치에서 현재 값을 선택할 수 있는 경우의 수와 남은 K를 비교하며 수열을 구성해나갑니다.

마지막 원소는 남은 합 전체를 사용하면 됩니다.

Code

C#

using System;
using System.Collections.Generic;

class Program {
  static int[,,] cache = new int[221, 11, 221];
  static List<int> result = new List<int>();

  static int Dp(int now, int d, int sum) {
    if (d == 1)
      return now <= sum ? 1 : 0;

    if (cache[now, d, sum] != -1)
      return cache[now, d, sum];

    var ret = 0;
    for (var i = now; i <= sum; i++)
      ret += Dp(i, d - 1, sum - i);

    cache[now, d, sum] = ret;
    return ret;
  }

  static void Bt(int now, int d, int sum, int s) {
    if (d == 1) result.Add(sum);
    else {
      var tmp = Dp(now, d - 1, sum - now);
      if (tmp >= s) {
        result.Add(now);
        Bt(now, d - 1, sum - now, s);
      } else Bt(now + 1, d, sum, s - tmp);
    }
  }

  static void Main() {
    for (var i = 0; i < 221; i++) {
      for (var j = 0; j < 11; j++) {
        for (var k = 0; k < 221; k++)
          cache[i, j, k] = -1;
      }
    }

    var parts = Console.ReadLine()!.Split();
    var n = int.Parse(parts[0]);
    var m = int.Parse(parts[1]);
    var kVal = int.Parse(parts[2]);

    Bt(1, n, m, kVal);
    Console.WriteLine(string.Join(" ", result));
  }
}

C++

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

typedef vector<int> vi;

int cache[221][11][221];
vi v;

int dp(int now, int d, int sum) {
  if (d == 1)
    return now <= sum;

  int& ret = cache[now][d][sum];
  if (ret != -1)
    return ret;

  ret = 0;
  for (int i = now; i < sum + 1; i++)
    ret += dp(i, d - 1, sum - i);

  return ret;
}

void bt(int now, int d, int sum, int s) {
  if (d == 1) {
    v.push_back(sum);
  } else {
    int tmp = dp(now, d - 1, sum - now);
    if (tmp >= s) {
      v.push_back(now);
      bt(now, d - 1, sum - now, s);
    } else bt(now + 1, d, sum, s - tmp);
  }
}

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

  int n, m, k;
  cin >> n >> m >> k;

  memset(cache, -1, sizeof(cache));
  bt(1, n, m, k);

  for (size_t i = 0; i < v.size(); i++) {
    cout << v[i];
    if (i == v.size() - 1) cout << "\n";
    else cout << " ";
  }

  return 0;
}