C++의 이상한 프린터

<시간/>

이상한 프린터가 있다고 가정하면 몇 가지 요구 사항이 있습니다 -

프린터는 매번 동일한 문자의 시퀀스만 인쇄할 수 있습니다.
매 턴에서 프린터는 모든 위치에서 시작하고 끝나는 새 문자를 인쇄할 수 있으며 원래의 기존 문자를 덮습니다.

따라서 문자열이 소문자로 구성된 경우 우리의 임무는 인쇄에 필요한 최소 회전 수를 계산하는 것입니다.

따라서 입력이 "aaabba"와 같으면 2턴이 걸리고 먼저 aaaaa를 인쇄한 다음 문자를 교체하여 b를 인쇄합니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=s의 크기
n이 0과 같으면 0을 반환합니다.
n x n 차수의 2D 배열 dp 하나를 정의하고 이를 무한대로 채웁니다.
l 초기화의 경우 :=1, l <=n일 때 업데이트(l을 1씩 증가), −
- 초기화 i :=0, j :=l - 1, j
- l이 1과 같으면 dp[i, j] :=1
그렇지 않으면 l이 2와 같을 때 -
- dp[i, j] :=s[i]가 s[j]와 같으면 1, 그렇지 않으면 2
그렇지 않으면
- 초기화 k :=i의 경우 k
- 온도 :=dp[i, k] + dp[k + 1, j]
- dp[i, j] :=dp[i, j]의 최소값 및 (s[k]가 s[j]와 같을 때 temp – 1, 그렇지 않으면 temp.

dp[0, n - 1]을 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
class Solution {
public:
   int strangePrinter(string s) {
      int n = s.size();
      if(n == 0) return 0;
      vector < vector <int> > dp(n, vector <int>(n, INF));
      for(int l = 1; l <= n; l++){
      for(int i = 0, j = l - 1; j < n; i++, j++){
         if(l == 1){
            dp[i][j] = 1;
            }else if(l == 2){
               dp[i][j] = s[i] == s[j] ? 1 : 2;
            }else{
               for(int k = i; k < j; k++){
                  int temp = dp[i][k] + dp[k + 1][j];
                  dp[i][j] = min(dp[i][j], s[k] == s[j] ? temp - 1: temp);
               }
            }
         }
      }
      return dp[0][n - 1];
   }
};
main(){
   Solution ob;
   cout << (ob.strangePrinter("aaabba"));
}

입력

“2*”

C++의 이상한 프린터

예시

입력

출력