[BOJ-16500][DP] 문자열 판별 - Java

문제 바로가기

16500번: 문자열 판별

 

DP 엉엉

그래도 풀고야 말앗다

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Set<String> A = new HashSet<>();
        int[] dp = new int[101];

        String s = br.readLine();
        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            A.add(br.readLine());
        }

        for(int i = s.length() - 1; i >= 0; i--) {
            for(int j = i + 1; j < s.length(); j++) {
                if(dp[j] == 1) {
                    if(A.contains(s.substring(i, j))) dp[i] = 1;
                }
            }
            if(A.contains(s.substring(i))) dp[i] = 1;
        }
        System.out.println(dp[0]);
    }
}

이 문제에서 메모해 나갈건 부분 문자열이 목록 A의 문자열들로 이루어져있는지 여부입니다.

dp[i]는 s.substring(i)가 A의 문자열들로 이루어져 있으면 1, 아니면 0을 저장할겁니다.

 

끝에서부터 봐줍시다.

 

안쪽에 있는 반복문에서는 dp[1]인 경우를 찾아서 그 나머지 부분 문자열을 체크합니다.

s.substring(i)인 부분 문자열 안에서 dp[j]가 1인 경우를 봅시다. s.substring(j)가 A에 포함되어 있다는 의미고, 만약 s.substring(i, j)도 A에 포함되어 있다면 dp[i]도 1이 되는 것이져.

 

그리고 s.substring(i) 이 친구 자체가 A에 포함되어 있는지도 체크해주어야 하겠죠!

 

 

정답은 dp[0](문자열 s가 A들의 문자열로 이루어져있는지 여부)를 출력해주면 끝입니다.

 

 

 

 

어떤걸 메모하면서 해를 찾아 나갈지 정하는 연습을 많이 해야겠습니다~~~!!!

감사함니다!!!