[C++] 백준 17243번 Almost-K Increasing Subsequence

문제

수열 a1, a2, ... , an이 주어진다. 이때, 우리는 이 수열에서 0개 이상의 수를 지워서 새로운 수열 b1, b2, ... , bm을 만들 수 있다. 이때, 수열 b1, b2, ... , bm을 수열 a1, a2, ... , an의 Subsequence라고 부른다. 예를 들어, 수열 (1,2,4,5)의 Subsequence는 (1), (2, 5), (1, 2, 4, 5) 등이 있다.

우리는 수열 A = a1, a2, ... , an와 K가 주어질때 수열 A의 Longest Almost-K Increasing Subsequence의 길이를 구하고 싶다. Longest Almost-K Increasing Subsequence란, Almost-K Increasing Subsequence중 가장 길이가 긴 수열을 의미하며, Almost-K Increasing Subsequence는 다음과 같이 정의된다.

수열 B = b1, b2, ... , bm이 수열 A의 Subsequence라고 가정하자. 이때, 모든 i = 1, 2, ... , m−1에 대하여, bi > bi+1인 i의 개수가 K개 이하인 경우, 수열 B를 수열 A의 Almost-K Increasing Subsequence라고 정의한다.

입력

첫 줄에 n, K(1 ≤ n ≤ 500, 0 ≤ K ≤ n)가 주어진다.

두 번째 줄에 정수 a1, a2, ... , an(1 ≤ ai ≤ 109)이 주어진다.

출력

수열 A의 Longest Almost-K Increasing Subsequence의 길이를 출력하라.

풀이

가장 긴 증가하는 부분수열(LIS)와 유사한 문제이다.
다른점이라면 k번만큼 규칙을 어길 수 있다는 것과 1,2,4,4와 같이 값이 같아도 상관없다는 점이다.
cnt번 만큼 규칙을 어길 수 있을때 srt번째 숫자부터 마지막 숫자까지의 최대 Longest Almost-K Increasing Subsequence를 리턴하는 함수를 만든 후 메모이제이션을 하면 쉽게 해결할 수 있다. 부분수열은 1개부터 시작하므로 ret의 최솟값은 1이어야 한다.

#include <iostream>
#include <vector>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <cmath>
#define endl '\n'

using namespace std;

int n,k;
int arr[500];
int dp[501][501];

int solve(int srt, int cnt){
  int& ret = dp[srt][cnt];
  if (ret != -1) return ret;
  ret = 1;

  for (int i=srt+1; i<n; i++){
    if (arr[srt] > arr[i] && cnt > 0) ret = max(ret, solve(i,cnt-1)+1);
    if (arr[srt] <= arr[i]) ret = max(ret, solve(i,cnt)+1);
  }

  return ret;
}

int main(){
  ios_base :: sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  // ifstream cin;
  // cin.open("input.txt");

  cin >> n >> k;

  for (int i=0; i<n; i++){
    cin >> arr[i];
  }

  memset(dp, -1, sizeof(dp));

  cout << solve(0,k);
}