백준 21941[자바] java 문자열 제거

문제 링크: https://www.acmicpc.net/problem/21941

21941번: 문자열 제거

▶문제

지우고 싶은 문자열 S와 지울 수 있는 문자열 A1, A2,...,AM이 주어진다. 문자열 Ai들은 각자 Xi라는 점수를 가진다. 이때, 문자열 S를 삭제 연산을 이용하여 모두 제거하려고 한다.

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

1. 문자열 S의 부분 문자열 중에 문자열 Ai 가 존재한다면 해당하는 부분을 지우고 Xi 만큼의 점수를 얻는다(여러 부분 존재해도 한 번만 지운다).
2. 문자열 S에서 문자 하나를 지우고 점수를 1점을 얻을 수 있다.

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

• 문자열 S에서 문자열 "xyz" 하나를 지운다. 현재 총 얻은 점수는 5점이고 문자열 S는 "abc___xabc"가 된다. 이때, '_'는 문자가 지워진 자리를 의미한다.
• 문자열 S에서 문자열 "abc" 하나를 지운다. 현재 총 얻은 점수는 15점이고 문자열 S는 "______xabc"가 된다.
• 문자열 S에서 문자열 "abc" 하나를 지운다. 현재 총 얻은 점수는 25점이고 문자열 S는 "______x___"가 된다.
• 남은 문자들을 하나씩 지운다. 현재 총 얻은 점수는 26점이고 문자열 S는 빈 문자열이 된다.

문자열을 모두 제거하여 얻을 수 있는 최대 점수는 26점이다. 이보다 더 얻을 수 있는 점수는 없다.

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

---

▶입력

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

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

세 번째 줄부터 M+2 줄까지 문자열 Ai와 점수 Xi이 공백으로 구분되어 주어진다.

---

▶출력

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

---

▶해설

조건을 살펴보겠습니다.

1. 주어진 문자열에서 하나씩만 삭제 가능하다.

2. 지우지 않은 문자열은 1로 계산된다.

 

숫자를 키워나가며, 가장 큰 값을 찾는 DP 문제입니다. 

 

String.startsWith()을 사용하겠습니다. startsWith(String, index) -> 인자로 들어간 문자열이 index부터 탐색하기 시작했을 때  부합한 지 판별해주는 메서드입니다. 

 

만약 부합하다면 저희는 탐색을 시작한 index+cost(문자열을 뺐을 때 얻는 값)과 기존에 있던 값을 비교하여 큰 값을 찾아주면 됩니다. 아래와 같은 점화식이 만들어집니다. 

dp[i +now.s.length()] = Math.max(dp[i + now.s.length()], dp[i] + now.cost);

여기서 주의할 점은 탐색을 시작하기 전 아래의 과정을 거쳐야 합니다. 부합한 문자열이 없어 빼지 않았을 때 1을 더해주는 로직입니다. 

dp[i + 1] = Math.max(dp[i+1], dp[i] + 1);

전체 코드

import java.io.*;
import java.util.*;
class str{
    String s;
    int cost;
 
    public str(String s, int cost) {
        this.s = s;
        this.cost = cost;
    }
}
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader (new InputStreamReader (System.in));
 
        String s = br.readLine();
        int length = s.length();
        int m = Integer.parseInt(br.readLine());
        List<str> list = new ArrayList<>();
        for (int i=0 ; i < m; i++){
            String[] s1 = br.readLine().split(" ");
            String a = s1[0];
            int cost = Integer.parseInt(s1[1]);
            list.add(new str(a,cost));
        }
 
        int [] dp = new int[length+1];
        for (int i = 0; i < s.length(); i++){
            dp[i + 1] = Math.max(dp[i+1], dp[i] + 1);
            for (int j = 0; j < m; j++){
                str now = list.get(j);
                if (s.startsWith(now.s, i)){
                    dp[i +now.s.length()] = Math.max(dp[i + now.s.length()], dp[i] + now.cost);
                }
            }
        }
        System.out.println(dp[s.length()]);
    }
}