백준 21941번: 문자열 제거

문제 설명

• https://www.acmicpc.net/problem/21941
• 문자 하나를 제거하면 1점을 얻습니다.
  특정 문자열을 한번에 제거하면 주어진 점수를 얻습니다.
  모든 문자열을 제거해서 얻을 수 있는 최대 점수를 구하는 문제입니다.

접근법

• 문자열의 길이가 1000으로 크지 않아 O(N^2)방식으로 문제를 접근했습니다.
  dp[i]는 i번째 문자까지 고려했을 때 얻을 수 있는 점수의 최대값입니다.
  0부터 i까지 반복하는 j변수를 만들었을 때 만약 s.substring(j,i)가 한번에 제거가능하다면 dp[i]의 점수는 j-1번째까지의 점수 + 한번에 제거한 점수가 됩니다.

정답

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		int N = s.length();
		int M = Integer.parseInt(br.readLine());
		Map<String,Integer> score = new HashMap<String,Integer>();
		for (int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String key = st.nextToken();
			int value = Integer.parseInt(st.nextToken());
			if(score.containsKey(key) && score.get(key) < value) {
				score.replace(key, value);
			}else {
				score.put(key, value);
			}
		}
		int[] dp = new int[N+1];
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= i; j++) {
				String temp = s.substring(j-1,i);
				if(score.containsKey(temp)) {
					dp[i] = Math.max(dp[i], dp[j-1]+score.get(temp));
				}else {
					dp[i] = Math.max(dp[i],dp[i-1]+1);
				}
			}
		}
		System.out.println(dp[N]);
	}
}