[백준 16500번] 문자열 판별 (C++)

문제링크 : https://www.acmicpc.net/problem/16500

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = INT_MAX;

string s;
int N;
string arr[101];
int dp[101];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> s >> N;
    for(int i=0; i<N; i++) cin >> arr[i];

    dp[s.size()]=1;

    for(int i=s.size(); i>=0; i--)
    {
        for(int j=0; j<N; j++)
        {
            if(s.find(arr[j], i) == i && dp[i+arr[j].size()] == 1) //해당 문자 시작점 체크
            {
                dp[i]=1;
            }
        }
    }

    cout << dp[0];

    return 0;
}

 

어떻게 dp 식을 세워야 하는지 감이 잘 안 잡혔던 문제이다.

다른 사람들의 풀이를 보고 이해를 했다.

아직 문자열과 섞인 dp에는 많이 약한 것 같다.

 

해당 위치에 해당 문자열이 있는가 없는가를 통하여 dp 값을 설정한다.

만약 해당 위치에 software이라는 문자가 존재한다면 문자의 시작점에 해당하는 위치인 s에 1을 할당하여 가능하다는 것을 나타낸다.

바로 뒤인 o나 f의 경우 해당 문자의 시작점이 아니므로 0을 할당하게 된다.

s o f t w a r e c o n t e s t
1 0 0 0 0 0 0 0 1 0 0 0 0 0 0

 

추가적으로 탐색 대상 문자인 s에 길이에 해당하는 위치에도 1을 할당해준다.

이후 입력된 문자의 위치 + 해당 문자열의 길이 값이 s의 마지막에 해당하는 위치에 해당하는 지 체크하는 용도로 사용된다. (문자열이 존재하고, 또 해당 문자열이 올바른 위치에 존재하는가 판별하기 위함)

 

따라서 먼저 find 함수를 이용하여 입력받은 문자열이 존재하는지를 판별하고, 또 해당 문자의 시작 인덱스를 찾는다.

이어서 단순히 해당 문자가 존재하는 것 뿐만이 아닌, dp[i+arr[j].size()]==1을 하여, 해당 문자가 올바른 위치에 있는 지 추가적인 판별을 거쳐 두 조건 모두 성립한다면 해당 인덱스에 해당하는 dp 값을 1로 바꿔준다.

 

이를 반복문에서 문자열 맨 뒤에서부터 탐색을 거치며, 결과적으로 맨 앞에 해당하는 dp[0]에 가능 불가능 여부가 담기게 된다.

따라서 dp[0]을 출력하면 해당 값이 정답이 된다.