글 읽기 - 시간초과 해결 도움이 필요합니다

smucs13 4년 전 0

시간초과 안나려면 어떻게 개선해야할까요?

도와주시면 감사하겠습니다

tc 1번 4번은 나오는데

2번 3번은 무한루프를 도는건지 출력이 안됩니다ㅠ

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

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

using namespace std;

int N, len, ans;
bool check[10];
vector<char> v, num;
vector<string> Input;

int solution() {
	int sum = 0;
	for (int i = 0; i < Input.size(); i++) {
		string str = Input[i];
		string temp = "";
		for (int j = 0; j < str.size(); j++) {
			auto it = find(v.begin(), v.end(), str[j]);
			temp += num[it - v.begin()];
		}
		sum += stoi(temp);
	}
	return sum;
}

void dfs(int cnt) {
	if (cnt == len) {
		int ret = solution();
		ans = max(ans, ret);
		return;
	}
	for (int i = 9; i >= 10-len; i--) {
		if (check[i]) continue;
		check[i] = true;
		num.push_back(i + '0');
		dfs(cnt + 1);
		num.pop_back();
		check[i] = false;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> N;
	for (int i = 0; i < N; i++) {
		string str;
		cin >> str;
		Input.push_back(str);
		for (int j = 0; j < str.size(); j++) {
			v.push_back(str[j]);
		}
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());	// 중복제거 + 쓰레기값 삭제
	len = v.size();

	dfs(0);
	cout << ans << '\n';
	return 0;
}

nahwasa 4년 전 1

분류가 백트래킹이긴하던데 왠지는 잘 모르겠습니다.

그리디에 더 가깝다고 생각되네요.

사실상 dfs가 필요없는 문제입니다.

요지는 N이 최대 10개라는 점 입니다. 그 이상이었으면 풀이가 좀 달랐겠네요.

즉,

..(전부 B 하나)

아래와 같이 N이 10개 있더라도 무조건 자리수 높은 문자에 높은 수를 주면 됩니다.

A=9, B=8과 A=8, B=9의 결과는 동일하므로

자리수 높은 문자에 높은 수를 주면 N=9이하일 경우 무조건 정답, N=10이더라도 못해도 동일한값이므로 역시 정답입니다.

이걸 힌트로 어떻게 풀이할지 생각해보심 좋을 듯 합니다.

smucs13 4년 전 0

seongjuk

저 아직 해결 못했습니다 제출은 다른사람 코드보려고 구글에서 정답긁어다가 냈습니다. 암튼

완전탐색으로 꼭 풀어야 맘이 편할 것 같아요 정말 감사합니다!!

nahwasa 4년 전 0

seongjuk

어 그렇네요.. 왜 통과됬지 ㄷㄷ

감사합니다!

ny2485 1년 전 0

저렇게 그리디적으로만 푸니 반례에 걸리는게 있는데.. 아직 헤어나오질 못하고있네요..

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

문제

문제

출처

ICPC

시간초과 해결 도움이 필요합니다

smucs13 4년 전 0

nahwasa 4년 전 1

smucs13 4년 전 0

seongjuk

nahwasa 4년 전 0

seongjuk

ny2485 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말