[LeetCode] 664. Strange Printer

https://leetcode.com/problems/strange-printer/description/?envType=daily-question&envId=2024-08-21

leetcode - Strange Printer

문제 유형 : 문자열 처리, 재귀, 다이나믹 프로그래밍, 투 포인터

문제 난이도 : Hard

 

문제

There is a strange printer with the following two special properties:

• The printer can only print a sequence of the same character each time.
• At each turn, the printer can print new characters starting from and ending at any place and will cover the original existing characters.

Given a string s, return the minimum number of turns the printer needed to print it.

 

두 개의 특징을 가진 이상한 프린터가 있다.

한 번에 한 가지 글자만 일련으로 출력할 수 있다.

출력된 문자열의 부분문자열을 다른 문자로 대체할 수 있다.

 

문자열 s가 주어지는데, 이 프린터로 인쇄하기 위해 필요한 동작횟수를 구하시오.

 

풀이

dp[from][to] = 인덱스 from부터 to까지의 부분문자열을 만들기 위한 최소 동작횟수라고 지정하여서 n x n 크기의 2D배열 dp를 만든다.

재귀 함수로 (0, n-1, s)부터 시작시킨다. 이러면 문자열 전체를 만들기 위한 최소 동작횟수를 구하는 것이다.

 

재귀 함수는 다음과 같이 동작한다:

  만약 from이 to보다 크다면, 유효하지 않으므로, 0을 반환하라.

  만약 dp[from][to]를 이미 구한 적 있다면, dp[from][to]를 반환하라.

  dp[from][to]를 처음에 solve(from + 1, to, s) + 1로 저장시킨다. 이는 그냥 s[from]의 글자를 1개 출력한다는 의미이다.

  그리고, from + 1부터 to까지 다음을 조사한다. 이를 반복하는 변수를 i라 하자.:

    s[from]과 s[i]가 같다면, from부터 i까지 같은 문자를 출력하고, 중간의 문자열을 만들기 위한 최소 동작횟수를 구하여 더하면 된다. 그리고 i+1부터 to까지의 부분문자열을 만들기 위해서 최소 동작횟수를 구해서 더하면 된다.

    즉, solve(from, i-1, s) + solve(i+1, to, s)를 dp[from][to]와 비교해서 최소값을 dp[from][to]에 업데이트하면 된다.

  

  위 과정들을 거치고, dp[from][to]를 반환하라.

 

아래는 s = "tbgtgb"에 대한 시각화이다. 가장 최소를 구하는 경우의 수 호출만 적었다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
private:
    vector<vector<int>> dp;
public:
    int solve(int from, int to, string &s) {
        if (from > to) return 0;
        if (dp[from][to] != -1) return dp[from][to];

        dp[from][to] = solve(from + 1, to, s) + 1;
        for (int i = from + 1; i <= to; ++i) {
            if (s[from] == s[i]) {
                dp[from][to] = min(dp[from][to], solve(from, i - 1, s) + solve(i + 1, to, s));
            }
        }
        return dp[from][to];
    }

    int strangePrinter(string s) {
        int n = s.size();
        dp.resize(n, vector<int>(n, -1));
        return solve(0, n - 1, s);
    }
};