백준 16500번: 문자열 판별

문제 설명

• https://www.acmicpc.net/problem/16500
• 작은 문자열들을 조합해 특정 문자열을 만들 수 있는지 판별하는 문제입니다.

접근법

• 타겟 문자열 S를 앞에서부터 한글자씩 늘려가며 판별하다가 A에 포함된 문자열이 되면 이후의 문자열이 다시 A에 포함되는지 확인하는 재귀를 생각했습니다.

  • s,so,sof,soft,...순서로 탐색하다가 software는 A에 존재하기 때문에 남은 문자열인 contest를 재귀함수에 넣어 다시 c,co,con,cont,...순서로 탐색했습니다.
  • 이 경우 시간초과가 발생합니다. 만약 aaaaaaaaaaaa...를 판별하기 위해 a,aa,aaa,aaaa,...와 같은 A가 주어진다면 너무나도 많은 재귀를 탐색해야 하기 때문입니다.

• 특정 인덱스까지 문자열을 이미 만들어봤다면 해당 문자열로 만든 이후과정을 다시 반복하지 않습니다.

  • soft,ware,software,contest로 softwarecontestx가 가능한지 판단해 봅시다.
    • soft가 먼저 등장하고 남은 warecontest로 다시 재귀를 실행합니다.
      다음으로 ware가 등장하고 남은 contestx로 재귀를 타 불가능하다는 게 밝혀졌습니다.
    • 이후 탐색에서 software가 등장합니다. 이는 soft+ware조합으로 이미 불가능하다는 걸 확인했기 때문에 contestx를 다시 검증하지 않습니다.
  • dp[i]이 true면 문자열 S의 부분문자열 S.substring(0,idx)을 A에 주어진 문자열로 만들 수 있다는 의미입니다.
    dp[8] = true면 softwarecontest의 부분문자열 software를 A에서 주어진 문자열들로 만들 수 있다는 뜻입니다.
    dp[i]가 true면 이미 이후의 문자열(S.substring(idx,S.length()))이 A로 만들어질 수 있는지를 판별했다는 의미이기 때문에 한번 더 판별하지 않습니다.

정답

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String S = br.readLine();		
		int N = Integer.parseInt(br.readLine());
		String[] arr = new String[N];
		for (int i = 0; i < N; i++) {
			arr[i] = br.readLine();
		}
		int[] dp = new int[S.length()]; // 정답을 손쉽게 출력하기 위해 boolean이 아니라 int를 사용했습니다.
		recursion(S,arr,dp,0);
		System.out.println(dp[S.length()-1]);
	}
	public static void recursion(String s, String[] arr,int[] dp, int startIdxOfThisRecursion) {
		// 재귀를 실행할 때 잘린 문자열로 판별하기 때문에 dp와의 인덱스가 어긋납니다.
		// software를 true로 만들고 contest를 판별할 때 contest에 대해서 c는 0번 idx지만 전체로 봤을때는 8번 idx입니다.
		// 이를 맞추기 위해 startIdxOfThisRecursion를 활용합니다.
		for (int i = 1; i <= s.length(); i++) {
			for (int j = 0; j < arr.length; j++) {
				if(arr[j].equals(s.substring(0,i)) && dp[startIdxOfThisRecursion+i-1] == 0) {
					dp[startIdxOfThisRecursion+i-1] = 1;
					recursion(s.substring(i,s.length()),arr,dp,startIdxOfThisRecursion+i);
				}
			}
		}

	}
}