팔굽혀펴기

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

(1)DP로 풀어야 한다는 것, (2)CACHE 정의를 어떻게 세워야 한다는 것, (3)점화식을 어떻게 세워줘야 한다는 것 모두를 어렵지 않게 떠올릴 수 있었다.

하지만, Iterative bottom-up DP를 고집하는 바람에 시간초과를 2번이나 맞았다.

때때로, Iterative bottom-up DP는 필요 없는 경우까지 구하는 경우가 있음을 상기하도록 하자.

보다 친숙한 표현으로 적어보자면, 전체 문제 공간에서 풀어야할 부분 문제들이 sparse해보이는 경우 Recursive top-down DP를 고려하자. 정도 되시겠다.

CACHE의 정의는 아래와 같이 해줄 수 있다.

• CACHE[n][s]: n번의 팔굽혀 펴기를 통해 s점을 획득할 수 있는가? (boolean)

점화식은 아래와 같이 세워줄 수 있다.

• CACHE[n][s] |= CACHE[n - s][s - s_i] (for all 0 <= i < M)

점화식은 아래와 같이 이해할 수 있다.

• n번의 팔굽혀펴기로 s점을 획득할 때, 맨 마지막 득점이 s_i였다고 해보자.
• 자명하게 직전에 팔굽혀펴기 횟수는 n-s번이 되어야 한다(s번을 더 해서 총 n번이 되어야 하므로).
• 역시나 자명하게 마지막 득점이 s_i라면 직전의 점수는 s-s_i가 되어야 한다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

const int kMaxN = 5000;
const int kTrue = 1;
const int kFalse = 2;
const int kUndefined = 0;

int N, M;
vector<int> SCORES;
int CACHE[kMaxN + 1][kMaxN + 1];

int Solve(const int n, const int s)
{
  int& ret = CACHE[n][s];
  if (ret != kUndefined)
  {
    return ret;
  }

  ret = kFalse;
  for (const auto& score : SCORES)
  {
    if (n >= s && s >= score && n - s >= s - score)
    {
      if (Solve(n - s, s - score) == kTrue)
      {
        ret = kTrue;
        break;
      }
    }
  }

  return ret;
}

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

  int testcase;
  cin >> testcase;

  while (testcase--)
  {
    memset(CACHE, 0, sizeof(CACHE));

    cin >> N >> M;
    SCORES.assign(M, 0);
    for (auto& score : SCORES)
    {
      cin >> score;
    }

    CACHE[0][0] = kTrue;

    int ans = -1;
    for (int s = N; s >= 0; --s)
    {
      if (Solve(N, s) == kTrue)
      {
        ans = s;
        break;
      }
    }

    cout << ans << '\n';
  }

  return 0;
}