글 읽기 - 속도향상 힌트 좀 주세요!!ㅠㅠ

his130 6년 전 0

로직은

찾으려는 위치의 첫글자가 같으면 나머지 비교하고,

비교해서 다 맞으면 재귀로 그 다음부터 비교하는 방식으로 구현했습니다.

시간초과를 해결할 방법이 뭐가 있을까요?

#include<iostream>
#include<string>
#include<vector>

using namespace std;
bool chk = false;
string v[114] = { "h","he","li","be","b","c","n","o","f","ne","na","mg","al","si","p","s","cl","ar","k","ca","sc","ti","v","cr","mn","fe",
"co","ni","cu","zn","ga","ge","as","se","br","kr","rb","sr","y","zr","nb","mo","tc","ru","rh","pd","ag","cd","ln","sn","sb","te","i","xe",
"cs","ba","hf","ta","w","re","os","lr","pt","au","hg","tl","pb","bi","po","at","rn","fr","ra","rf","db","sg","bh","hs","mt","ds","rg","cn","fl","lv",
"la","ce","pr","nd","pm","sm","eu","gd","tb","dy","ho","er","tm","yb","lu","ac","th","pa","u","np","pu","am","cm","bk","cf","es","fm","md","no","lr" };


void go(string s,int end, int pos)
{
	if (chk)
	{
		return;
	}
	if (pos > end)
	{
		return;
	}
	if (pos == end)
	{
		chk = true;
		return;
	}

	for (int i = 0; i < 114; i++)
	{
		if (v[i][0] == s[pos])
		{
			bool gogo = true;
			int j, tmp_pos;
			for (j = 0, tmp_pos = pos; j < v[i].size(); j++,tmp_pos++)
			{
				if (v[i][j] != s[tmp_pos])
				{
					gogo = false;
					break;
				}
			}

			if (gogo)
			{
				go(s, end, pos + j);
			}
		}
	}

}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	//freopen("input.txt", "r", stdin);
	int n;
	cin >> n;

	
	for (int i = 0; i < n; i++)
	{
		string tmp;
		cin >> tmp;
		chk = false;
		go(tmp,tmp.size(), 0);
		if (chk) 
		{
			cout << "YES" << "\n";
		}
		else
		{
			cout << "NO" << "\n";
		}
		
	}
	
	return 0;
}

chogahui05 6년 전 0

i번째 loc까지 어떻게 어떻게~~ 맞췄다고 가정했을 때.
그 다음에는 어떻게 해야 할까요?

his130 6년 전 0

음.. 말씀해주신게 어떤말인지를 잘 이해를 못했습니다..

ㅠㅠ

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

문제

문제

출처

ICPC

속도향상 힌트 좀 주세요!!ㅠㅠ

his130 6년 전 0

chogahui05 6년 전 0

his130 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말