[백준] 16500번 문자열 판별 (자바 풀이)

문제

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

16500번: 문자열 판별

 

풀이

이 문제는 아래와 같이 DP를 사용하여 해결할 수 있다.

 

 

 

1. A에 있는 문자열을 HashSet 자료구조에 모두 저장한다. 

2. S의 뒷자리부터 0까지 순서대로 문자열을 substring으로 잘라 A에 속해있는지 확인한다.

 ex) t, st, est, test, ntest, ontest, contest .....

3. 만약 substring이 A에 속해있다면 해당 dp 배열의 원소를 1로 바꿔준다.

4. dp[0]을 출력한다.

 

 

코드

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


public class Baekjoon_16500 {
	static int N;
	static String S;
	static int[] dp = new int[101];
	static Set<String> set = new HashSet<>();
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		S = br.readLine();
		
	    N = Integer.parseInt(br.readLine());
		
		for(int i=0; i<N; i++) {
			set.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(set.contains(S.substring(i,j))) {
						dp[i] = 1;
					}
				}
			}
			
			if(set.contains(S.substring(i))){
				dp[i] = 1;
			}
		}
		
		System.out.println(dp[0]);
		
	}

}