Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 이상한 프린터 문제 풀이: 구간 DP로 최소 출력 횟수 구하기

문제 소개

동작 방식이 조금 특이한 '이상한 프린터(Strange Printer)'가 있다고 가정해 봅시다. 이 프린터에는 다음과 같은 제약 조건이 있습니다.

  • 프린터는 한 번에 같은 문자로만 이루어진 연속된 문자열을 출력할 수 있습니다.
  • 각 차례마다 임의의 시작 위치와 끝 위치를 골라 새 문자를 출력할 수 있으며, 해당 범위에 이미 출력되어 있던 문자는 모두 덮어쓰기 됩니다.

소문자 알파벳으로만 구성된 문자열이 주어졌을 때, 이 문자열 전체를 완성하기 위해 필요한 최소 출력 횟수를 구하는 것이 우리의 목표입니다.

예를 들어 입력이 “aaabba”라면 정답은 2입니다. 첫 번째 차례에 “aaaaaa”를 출력한 후, 두 번째 차례에 가운데 두 칸을 'b'로 덮어쓰면 원하는 문자열이 완성되기 때문입니다.

풀이 접근: 구간 동적 계획법(DP)

이 문제는 짧은 구간의 답을 이용해 긴 구간의 답을 만들어 나가는 대표적인 구간 DP(Interval DP) 유형입니다. dp[i][j]를 “i번째 문자부터 j번째 문자까지의 구간을 출력하는 데 필요한 최소 횟수”로 정의하면, 구간을 분할 지점 k를 기준으로 둘로 나누어 결합하는 방식으로 점화식을 세울 수 있습니다.

구체적인 알고리즘은 다음과 같습니다.

  1. n := 문자열 s의 길이로 설정합니다.
  2. n이 0이라면 0을 반환합니다.
  3. n × n 크기의 2차원 배열 dp를 선언하고 무한대(INF)로 초기화합니다.
  4. 구간 길이 l을 1부터 n까지 1씩 늘려가며 다음을 반복합니다.
    • i := 0, j := l − 1에서 시작해 j < n인 동안 i와 j를 1씩 증가시키며 반복합니다.
      • l == 1이면: dp[i][j] := 1 (길이 1짜리 구간은 한 번에 출력할 수 있습니다.)
      • l == 2이면: s[i] == s[j]일 때 dp[i][j] := 1, 그렇지 않으면 2
      • 그 외의 경우: k를 i부터 j − 1까지 순회하며 temp := dp[i][k] + dp[k+1][j]를 계산합니다. 이때 s[k] == s[j]라면 temp − 1을, 아니라면 temp를 후보로 삼아 dp[i][j]를 최솟값으로 갱신합니다.
  5. 모든 반복이 끝나면 dp[0][n − 1]을 반환합니다.

여기서 핵심 아이디어는 분할 지점 k에서 s[k]와 s[j]가 같다면, 오른쪽 구간 [k+1, j]를 채우는 마지막 출력이 왼쪽 구간 [i, k]의 끝부분까지 함께 덮을 수 있다는 점입니다. 이렇게 하면 출력 횟수를 1회 절약할 수 있습니다.

C++ 구현 예제

#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"));
}

입력 및 실행 결과

위 코드는 문자열 “aaabba”에 대해 strangePrinter 함수를 호출합니다.

출력

2

“aaaaaa”를 먼저 출력한 뒤 'b' 두 글자를 덮어쓰는 방식으로, 총 2번의 출력만으로 목표 문자열을 완성할 수 있습니다.

복잡도 분석

구간 길이 l, 시작점 i, 분할 지점 k를 모두 순회하므로 시간 복잡도는 O(n³)이며, 2차원 DP 테이블을 사용하므로 공간 복잡도는 O(n²)입니다. 문자열 길이가 수백 수준이라면 충분히 실용적인 성능을 보입니다.