글 읽기 - 메모이제이션을 도와주세요..

kkw564 7년 전 0

진짜 최적화 했다고 생각하는데 어디를 더 손봐야할까요.. ㅠ

bfs로 풀었습니다.

#include <iostream>
#include <cstdio>
#include <string>
#include <queue>

using namespace std;
typedef pair<pair<string, int>, pair<int, int>> psi;

int main()
{
	int n;
	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
	{
		string strA, strB, strC;

		cin >> strA >> strB >> strC;

		int lenA = strA.size();
		int lenB = strB.size();
		int lenC = lenA + lenB;

		bool yes = false;

		queue<psi> q;

		string tmp1;
		tmp1 += strA[0];
		string tmp2;
		tmp2 += strB[0];

		q.push({ {tmp1, 0}, {0, 0} });
		q.push({ {tmp2, 0}, {0, 0} });

		while (!q.empty())
		{
			string str = q.front().first.first;
			int pos = q.front().first.second;
			int posA = q.front().second.first;
			int posB = q.front().second.second;

			q.pop();

			// cout << "거르기 전 :: " << str << endl;
			if (str[pos] != strC[pos])
				continue;

			// cout << "거르기 후 :: " << str << endl;
			if (pos + 1 == lenC && str.compare(strC) == 0)
			{
				yes = true;
				break;
			}

			if (posA + 1 < lenA)
			{
				if(strA[posA + 1] == strC[pos + 1])
					q.push({ {str + strA[posA + 1], pos + 1}, {posA + 1, posB} });

				if(posB < lenB && strB[posB] == strC[pos + 1])
					q.push({ { str + strB[posB], pos + 1 },{ posA + 1, posB } });
			}
			if (posB + 1 < lenB)
			{
				if(strB[posB + 1] == strC[pos + 1])
					q.push({ {str + strB[posB + 1], pos + 1}, {posA, posB + 1 } });

				if(posA < lenA && strA[posA] == strC[pos + 1])
					q.push({ { str + strA[posA], pos + 1 },{ posA + 1, posB } });
			}
		}

		if (yes)
			printf("Data set %d: yes\n", i);
		else
			printf("Data set %d: no\n", i);
	}
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

메모이제이션을 도와주세요..

kkw564 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말