글 읽기 - 1134번 질문드립니다

sjy1602 6년 전 0

string을 3개로 나눠서 물음표가 없을 때 까지 0 ~ 9 까지 대입해가면서 찾는 방법을 사용했는데

시간초과가 나오네요 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

이런식으로 접근하면 안되는 건가요 ㅠㅠㅠ 어떤 방식이 있을까요?

고수님들 조언 부탁드립니다

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int quesCnt = 0;
string str[3];
int result1 = -1, result2 = - 1, result3 = - 1;

void solve(int depth);

int main()
{
	int cnt = 0;
	while (1)
	{
		char ch;
		ch = getchar();

		if (ch == '?')
			quesCnt++;

		if (ch == '\n')
			break;

		else if (ch == '+' || ch == '=')
			cnt++;
		else
			str[cnt] += ch;
	}

	solve(0);

	if (result1 == -1 || result2 == -1)
		cout << -1;
	else
		cout << result1 << "+" << result2 << '=' << result3 << endl;
}

void solve(int depth)
{
	int strPos[3];
	strPos[0] = str[0].find('?');
	strPos[1] = str[1].find('?');
	strPos[2] = str[2].find('?');

	if (strPos[0] == str[0].npos && strPos[1] == str[1].npos && strPos[2] == str[2].npos)
	{
		if (atoi(str[0].c_str()) + atoi(str[1].c_str()) == atoi(str[2].c_str()))
		{
			if (atoi(str[2].c_str()) > result3)
			{
				result1 = atoi(str[0].c_str());
				result2 = atoi(str[1].c_str());
				result3 = atoi(str[2].c_str());
			}
			else if (atoi(str[2].c_str()) == result3)
			{
				if (atoi(str[0].c_str()) > result1)
				{
					result1 = atoi(str[0].c_str());
					result2 = atoi(str[1].c_str());
					result3 = atoi(str[2].c_str());
				}
			}
		}
		return;
	}

	for (int i = 0; i < 3; i++)
	{
		if (strPos[i] == str[i].npos)
			continue;
		
		for (int j = 0; j < 10; j++)
		{
			str[i][strPos[i]] = j + 48;
			solve(depth + 1);
			str[i][strPos[i]] = '?';
		}
	}
}

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

문제

문제

출처

ICPC

1134번 질문드립니다

sjy1602 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말