[알고리즘] 백준 > #16500. 문자열판별

피곤해죽을거같지만 문제를 풀었다 ㅠ

문제링크

백준 #16500. 문자열판별

풀이방법

테스트케이스가 딱 하나다. 그리고 그 테스트케이스는 너무 불친절해서 문제를 똑바로 이해하지 못하기 딱 좋다. 처음에 주어진 테스트케이스를 봤을때 그냥 사전 단어들을 시작 알파벳으로 정리하고 S 내에 매치되는거 확인하면되는거아냐? 라고 생각했는데 절대 아니었다.

aaaa
2
aa
aaa
이 케이스만 봐도 위 방법으로는 해결하지 못한다는 것을 알 수 있다.

그러다 S를 앞에서 뒤로 하나씩 늘린다는 생각을 하게 되었고, DP까지 이어지게 되었다.
각 dp 값을 해당 위치까지 A 사전내 단어로 채울 수 있다면 T / 그렇지 않다면 F로 세팅했다.

위 풀이방법을 aaa 예시로 설명하자면, 다음 그림과 같다.

코드

import java.util.Scanner;

/**
 * @type: DP
 * @문제: https://www.acmicpc.net/problem/16500
 * @문제풀이: TODO
 */
public class StringDetermination {
    static String s;
    static int n;
    static String[] a;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        s = sc.nextLine();

        n = Integer.parseInt(sc.nextLine());
        a = new String[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLine();
        }

        boolean[] isPossibleWord = new boolean[s.length() + 1];
        isPossibleWord[0] = true;

        for (int i = 0; i < s.length(); i++) {
            int prefixLength = i + 1;

            for (int j = 0; j < n; j++) {
                if ((prefixLength >= a[j].length()) &&
                        s.substring(i - a[j].length() + 1, i + 1).equals(a[j])) {
                    if (isPossibleWord[prefixLength - a[j].length()]) {
                        isPossibleWord[prefixLength] = true;
                        break;
                    }
                }
            }
        }

        int result;
        if (isPossibleWord[s.length()]) result = 1;
        else result = 0;

        System.out.println(result);
    }
}

내일도 풀어야징~