백준 16500번 _ 문자열 판별

2020-05-10 · 배운 것 · 4분 읽기

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

접근

이 문제를 완전탐색으로 푼다면 최악의 경우 100!으로 절대 시간안에 풀수없다.
잘 보면 중복연산이 매우매우 많으니 메모제이션을 사용하자!!

풀이방법

이 문제는 주어진 word들이 S를 만들수 있는지 없는지만 판별하면 되는 문제다.
그러므로 dp[string 길이] : -1일땐 아직 탐색안한것, 0일땐 탐색했는데 없는것, 1일때 탐색했는데 있는것 이렇게 세가지 형태로 두겠다. 그 이후에는 그냥 일반적인 **top down 방식 ( 재귀방식 )**으로 풀면 된다. 밑의 코드를 보면 일반적으로 자주쓰는 형태라는것을 알수있다. 자세하게 설명하기엔 전에 풀었던 문제들과 코딩형태가 너무 유사해서 생략했다.

int getPossibleOrNot(int pos)
{
	int& ret = dp[pos];
	if (ret != -1) return ret;

	//기저사례 : 여기까지 무사히 왔으면 있는겨
	if (pos == S.size()) return ret = 1;

	ret = 0;
	for (int i = 1; i <= N; i++)
	{
		if (compareEachOther(i, pos) == false)
			continue;
		int nextPos = pos + words[i].size();
		ret = max(ret, getPossibleOrNot(nextPos));
	}
	return ret;
}

확실한 풀이를 보고싶다면 밑의 풀이에서 완전탐색부터 시작해서 재귀방식으로 푸는것까지 자세하게 풀어놓았으니 이걸 보면 좋겠다. 잘 보면 거의 유사하다
https://blog.fxjodo.com/blog/80/

알고스팟_ 와일드 카드_ 종만북_DP

전체코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int dp[101];
string S;
string words[101];
int N;

void dpInit()
{
	for (int i = 0; i <= S.size(); i++)
		dp[i] = -1;
}

void Input()
{
	cin >> S;
	cin >> N;
	for (int i = 1; i <= N; i++)
		cin >> words[i];
}

bool compareEachOther(const int& wordIdx, const int& pos)
{
	int wordSize = words[wordIdx].size();
	//word가 남은 문장보다 길면 당연히 false
	if (wordSize > S.size() - pos)
		return false;

	//비교 ㄱㄱ
	string word = words[wordIdx];
	for (int i = 0; i < wordSize; i++)
		if (word[i] != S[pos + i])
			return false;
	return true;
}

int getPossibleOrNot(int pos)
{
	int& ret = dp[pos];
	if (ret != -1) return ret;

	//기저사례 : 여기까지 무사히 왔으면 있는겨
	if (pos == S.size()) return ret = 1;

	ret = 0;
	for (int i = 1; i <= N; i++)
	{
		if (compareEachOther(i, pos) == false)
			continue;
		int nextPos = pos + words[i].size();
		ret = max(ret, getPossibleOrNot(nextPos));
	}
	return ret;
}

int main()
{
	Input();
	dpInit();
	cout << getPossibleOrNot(0);
	return 0;
}

후기

처음에는 어떻게 접근해야 할지 엄청 막막했다. 하지만 잘 보니까 종만북에서 자주보던 dp풀이로 풀수있을것같아서 그렇게 풀어보았다.