ABC

Problem link: https://www.acmicpc.net/problem/12969

딱봐도 내가 잘하지 못하는 유형(DP + 백트래킹)의 문제임을 알 수 있어서 순간 쫄았었다.

하지만, 마침 14238번 출근 기록 문제를 푼 직후라서 그런지 나름대로 빠른 시간 내에 풀 수 있었다.

출근 기록 문제에서와 유사하게(사실 그렇게 비슷하지는 않지만) Top down DP로 풀어주었다.

우선, 아래와 같이 DP Cache를 정의해주었다.

• CACHE[na][nb][nc][k]: A를 na개, B를 nb개, 그리고 C를 nc개 사용하였을 때, 조건을 만족하는 순서쌍이 정확히 k개 있는 문자열을 만들 수 있는가?

점화식의 아이디어는 각 DP step에서 문자열의 맨 마지막에 추가할 문자를 정하는 것이다.

예를 들어, 문자열의 맨 마지막에

• Case 1) A를 놓는다면 ...A와 같은 형태가 될 것이고, A가 추가됨으로 인해서 새로 생겨나는 순서쌍은 없다.
• Case 2) B를 놓는다면 ...B와 같은 형태가 될 것이고, B가 추가됨으로 인해서 이전 문자열에 존재하는 A의 수만큼 순서쌍이 새로 생겨난다.
• Case 3) C를 놓는다면 ...C와 같은 형태가 될 것이고, C가 추가됨으로 인해서 이전 문자열에 존재하는 A, B의 수만큼 순서쌍이 새로 생겨난다.

이를 코드로 옮기면 아래와 같다.

• CACHE[na][nb][nc][k]=CACHE[na-1][nb][nc][k] | CACHE[na][nb-1][nc][k-na] | CACHE[na][nb][nc-1][k-na-nb]

or로 연결된 각 항이 곧 Case 1, 2, 3에 대응되는 것을 쉽게 알 수 있다.

CACHE[na][nb][nc][K]==True가 되게하며 na + nb + nc = N인 na, nb, nc가 존재한다면 해가 존재한다.

해의 존재성을 알아내었다면, 이제 다시 백 트래킹을 통하여 실제 답을 구해주도록하자.

사실상 DP 연산과 동일하므로 별도의 설명은 첨부하지 않는다.

#include <iostream>
#include <string>

using namespace std;

const int kMaxN = 30;
const int kMaxK = 15 * 29;

const int kTrue = 1;
const int kFalse = 0;

int N;
int K;
int CACHE[kMaxN + 1][kMaxN + 1][kMaxN + 1][kMaxK + 1];

void InitializeCache()
{
  const size_t kSize = (kMaxN + 1) * (kMaxN + 1) * (kMaxN + 1) * (kMaxK + 1);
  int* const offset = &(CACHE[0][0][0][0]);
  for (size_t idx = 0; idx < kSize; ++idx)
  {
    offset[idx] = -1;
  }
}

bool IsPossible(const int na, const int nb, const int nc, const int k)
{
  if (na < 0 || nb < 0 || nc < 0 || k < 0)
  {
    return false;
  }

  if (na == 0 && nb == 0 && nc == 0 && k == 0)
  {
    return true;
  }

  int& ret = CACHE[na][nb][nc][k];
  if (ret != -1)
  {
    return (ret == kTrue);
  }

  ret = kFalse;

  if (IsPossible(na - 1, nb, nc, k))
  {
    ret = kTrue;
  }
  else if (IsPossible(na, nb - 1, nc, k - na))
  {
    ret = kTrue;
  }
  else if (IsPossible(na, nb, nc - 1, k - na - nb))
  {
    ret = kTrue;
  }

  return (ret == kTrue);
}

void Backtrack(const int na, const int nb, const int nc, const int k, string& str)
{
  if (na < 0 || nb < 0 || nc < 0 || k < 0)
  {
    return;
  }

  if (na == 0 && nb == 0 && nc == 0 && k == 0)
  {
    return;
  }

  if (IsPossible(na - 1, nb, nc, k))
  {
    Backtrack(na - 1, nb, nc, k, str);
    str += "A";
  }
  else if (IsPossible(na, nb - 1, nc, k - na))
  {
    Backtrack(na, nb - 1, nc, k - na, str);
    str += "B";
  }
  else if (IsPossible(na, nb, nc - 1, k - na - nb))
  {
    Backtrack(na, nb, nc - 1, k - na - nb, str);
    str += "C";
  }

  return;
}

string Solve()
{
  InitializeCache();

  for (int na = 0; na <= N; ++na)
  {
    for (int nb = 0; na + nb <= N; ++nb)
    {
      int nc = N - na - nb;

      if (nc >= 0 && IsPossible(na, nb, nc, K))
      {
        string ret = "";
        Backtrack(na, nb, nc, K, ret);
        return ret;
      }
    }
  }

  return string("-1");
}

int main(void)
{
  // For Faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read Input
  cin >> N >> K;

  // Solve
  cout << Solve() << '\n';

  return 0;
}