[백준] 16500 문자열 판별 🤔 (Java)

문제 링크

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

문제 설명

알파벳 소문자로 이루어진 문자열 S와 단어 목록 A가 주어졌을 때, S를 A에 포함된 문자열을 한 개 이상 공백없이 붙여서 만들 수 있는지 없는지 구하는 프로그램을 작성하시오. A에 포함된 단어를 여러 번 사용할 수 있다.

입력

첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 포함된 문자열은 알파벳 소문자로만 이루어져 있고, 길이는 100을 넘지 않는다.

출력

A에 포함된 문자열로 S를 만들 수 있으면 1, 없으면 0을 출력한다.

구조화

문자열의 끝까지 정확하게 매칭되어야 전체 문자열을 만들었다고 할 수 있음 → dp[s_len+1]

원래 dp top down으로 시도했는데, 백트래킹, 메모이제이션 다 시초남 -> 결국 bottom up으로..

소스 코드

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

public class Main {
    static int n, s_len;
    static int[] l;
    static String s;
    static String[] a;
    static boolean[] dp; // 각 위치에서 만들 수 있는지 여부를 저장하는 DP 배열

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        s = br.readLine();
        s_len = s.length();

        n = Integer.parseInt(br.readLine());

        a = new String[n];
        l = new int[n];

        for (int i = 0; i < n; i++) {
            a[i] = br.readLine();
            l[i] = a[i].length();
        }

        dp = new boolean[s_len + 1];
        dp[0] = true; // 시작 위치는 항상 true

        for (int i = 0; i < s_len; i++) {
            if (!dp[i]) continue; // 현재 위치에서 만들 수 없으면 넘어감

            for (int j = 0; j < n; j++) {
                int len = l[j];
                if (i + len <= s_len && s.startsWith(a[j], i)) {
                    dp[i + len] = true; // a[j]로부터 만들어진다면 해당 위치를 true로 설정
                }
            }
        }

        System.out.println(dp[s_len] ? 1 : 0);
    }
}