21941번. 문자열 제거

 

 

아이디어

지울 수 있는 문자열 중에 점수가 큰 것부터 지워나가면 되지 않을까 생각했지만 이런 그리디 방식의 탐색은

 

bab

2

bab 3

a 2

 

와 같은 사례에서는 통하지 않는다.

 

따라서 문자열 S 를 앞에서부터 탐색해가면서 지울 수 있는 문자열이 등장했을 때

이를 통으로 지우는 것 vs 단순히 문자 하나를 지우는 것 중 어떤 방법이 더 점수를 높게 가져갈 수 있는지를 확인하는 방식을 사용해야 한다.

 

dp[i] 를 문자열 S 에 대해 i 번째 문자까지 탐색했을 때 최대 점수 라고 정의한다면

 

dp[i] = Math.max(dp[i - 1] + 1, dp[i - 지울 수 있는 문자열의 길이] + 지울 수 있는 문자열의 점수)

 

가 된다.

 

풀이코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String S = br.readLine();
        int M = Integer.parseInt(br.readLine());

        String[] strings = new String[M];
        int[] points = new int[M];
        for (int i = 0; i < M; i++) {
            String[] input = br.readLine().split(" ");
            strings[i] = input[0];
            points[i] = Integer.parseInt(input[1]);
        }


        int[] dp = new int[S.length() + 1];

        for (int i = 1; i <= S.length(); i++) {
            char character = S.charAt(i - 1);

            dp[i] = dp[i - 1] + 1;
            for (int j = 0; j < M; j++) {
                String A = strings[j];

                if (S.startsWith(A, i - A.length())) {
                    dp[i] = Math.max(dp[i], dp[i - A.length()] + points[j]);
                }
            }
        }

        System.out.println(dp[S.length()]);
    }
}