[자바] 백준 21941 - 문자열 제거 (boj java)

문제 : boj21941

 

기존에 그리디로 생각해서 풀었었는데, 재채점이 되어 틀려있었다. 기존 틀린 풀이는 여기에 있다. 다시 풀어서 작성한다.

 

   문자열 s를 각 인덱스(이하 idx)를 정점으로 하는 가중치를 가지는 방향 그래프로 바꿔서 생각해보자. 이 때, '문자열 S에서 문자 하나를 지우고 점수를 1점을 얻을 수 있다.' 라는 부분은 idx -> idx+1 로 가는 가중치 1의 간선으로 바꿀 것이다. 그리고 문자열 Ai와 그에 따른 가중치는 예를들어 s가 "abcd"이고, A1이 bc이고 가중치가 3이라고 한다면 idx=1 -> idx=3으로 향하는 가중치 3의 간선이라고 할 수 있다.

 

  예제 입력 1을 봐보자.

abcxyzxabc
2
abc 10
xyz 5

  위에서 말한 그래프로 그려보면 다음과 같다.

  위와 같이 그래프로 만들고보면 결국 dfs 등의 그래프 순회 알고리즘을 통해 idx 0부터 goal 까지 향하는 모든 경우를 확인할 수 있게 된다. 그럼 goal 까지 향하는 모든 경우 중 그동안의 가중치 합산이 가장 높은 경우가 답이 될 것이다.

 

  다만 단순히 이렇게 하면 시간초과가 나게 된다. memoization을 더해서, 동일한 정점에 더 높거나 같은 가중치를 가지고 도착한 적이 있다면 더이상 진행하지 않는 백트래킹 방식도 추가해주면 시간내에 통과할 수 있다. (코드의 if (memoization[idx] >= weightSum) return; 부분)

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

class Edge {
    int to, weight;
    public Edge(int to, int weight) {
        this.to = to;
        this.weight = weight;
    }
}

public class Main {
    private int len;
    private ArrayList<Edge>[] edges;
    private int[] memoization;

    private void dfs(int idx, int weightSum) {
        if (memoization[idx] >= weightSum) return;
        memoization[idx] = weightSum;
        if (idx == len) {
            return;
        }
        for (Edge edge : edges[idx]) {
            dfs(edge.to, weightSum + edge.weight);
        }
    }
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        int n = Integer.parseInt(br.readLine());
        len = s.length();
        memoization = new int[len+1];
        Arrays.fill(memoization, -1);
        edges = new ArrayList[s.length()];
        for (int i = 0; i < s.length(); i++) {
            edges[i] = new ArrayList<>();
            edges[i].add(new Edge(i+1, 1));
        }
        StringTokenizer st;
        while (n-->0) {
            st = new StringTokenizer(br.readLine());
            String cur = st.nextToken();
            int weight = Integer.parseInt(st.nextToken());
            if (cur.length() >= weight) continue;
            for (int i = 0; i < len; ) {
                int idx = s.indexOf(cur, i);
                if (idx == -1) break;
                i = idx+cur.length();
                edges[idx].add(new Edge(i, weight));
            }
        }
        dfs(0, 0);
        System.out.println(memoization[len]);
    }
    public static void main(String[] args) throws Exception{
        new Main().solution();
    }
}