[Java] 백준 21941 문자열 제거

https://www.acmicpc.net/problem/21941

난이도

골드 4

문제

지우고 싶은 문자열
$S$와 지울 수 있는 문자열 $A_{1}$, $A_{2}$, ..., $A_{M}$이 주어진다. 문자열 $A_{i}$들은 각자 $X_{i}$라는 점수를 가진다. 이 때, 문자열 $S$를 삭제 연산을 이용하여 모두 제거하려고 한다.

삭제 연산은 두 가지 방법이 존재하며, 원하는 만큼 여러 번에 걸쳐서 수행할 수 있다.

문자열 $S$의 부분 문자열 중에 문자열 $A_{i}$ 가 존재한다면 해당하는 부분을 지우고 $X_{i}$ 만큼의 점수를 얻는다(여러 부분 존재해도 한 번만 지운다).

문자열 $S$에서 문자 하나를 지우고 점수를 $1$점을 얻을 수 있다.
예를 들어, 문자열 $S$가 "abcxyzxabc"이 있고 "abc" 문자열을 지울 경우 10점, "xyz" 문자열을 지울 경우 5점을 얻는다고 하자. 문자열을 모두 제거하여 최대 점수를 얻을 수 있는 과정은 아래와 같다.

문자열 $S$에서 문자열 "xyz" 하나를 지운다. 현재 총 얻은 점수는 5점이고 문자열
$S$는 "abcxabc"가 된다. 이때, ''는 문자가 지워진 자리를 의미한다.
문자열 $S$에서 문자열 "abc" 하나를 지운다. 현재 총 얻은 점수는 15점이고 문자열 $S$는 "____xabc"가 된다.문자열 $S$에서 문자열 "abc" 하나를 지운다. 현재 총 얻은 점수는 25점이고 문자열 $S$는 "__x___"가 된다.
남은 문자들을 하나씩 지운다. 현재 총 얻은 점수는 26점이고 문자열 $S$는 빈 문자열이 된다.
문자열을 모두 제거하여 얻을 수 있는 최대 점수는 26점이다. 이보다 더 얻을 수 있는 점수는 없다.

삭제 연산을 이용하여 문자열 $S$을 지울려고 할 때 얻을 수 있는 최대 점수는 몇 점인지 계산하자.

입력

첫번째 줄에는 문자열 $S$이 주어진다.

두번째 줄에는 지울 수 있는 문자열 개수 $M$이 주어진다.

세번째 줄부터 $M + 2$ 줄까지 문자열 $A_{i}$와 점수 $X_{i}$이 공백으로 구분되어 주어진다.

출력

문자열 $S$를 모두 제거하여 얻을 수 있는 점수를 출력하자.

코드

import java.io.*;
import java.util.*;

public class Main {

    static class Pattern {
        String w;
        int score;
        Pattern(String w, int score) {
            this.w = w;
            this.score = score;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String S = br.readLine().trim();
        int n = S.length();

        int M = Integer.parseInt(br.readLine().trim());
        List<Pattern> patterns = new ArrayList<>();
        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String w = st.nextToken();
            int p = Integer.parseInt(st.nextToken());
            patterns.add(new Pattern(w, p));
        }

        List<Pattern> useful = new ArrayList<>();
        for (Pattern pat : patterns) {
            if (pat.score > pat.w.length()) useful.add(pat);
        }
        if (!useful.isEmpty()) patterns = useful;

        int[] dp = new int[n + 1]; // dp[n] = 0 (기저)

        for (int i = n - 1; i >= 0; i--) {
            // 1) 문자 1개 그냥 지우기
            dp[i] = dp[i + 1] + 1;

            // 2) 등록된 패턴이 i에서 시작하면 사용
            for (Pattern pat : patterns) {
                int len = pat.w.length();
                if (i + len <= n && S.startsWith(pat.w, i)) {
                    dp[i] = Math.max(dp[i], pat.score + dp[i + len]);
                }
            }
        }

        System.out.println(dp[0]);
    }
}