글 읽기 - 시간 초과가 나는 이유

paparoni 2년 전 0

간단하게 풀이과정을 설명하면

1 <= i < j < m 조건에 맞는 순서쌍을 모두 pos에 저장합니다.

이후 백트래킹을 이용해서 k가 총 10번 연산할 수 있으니 10개의 순서쌍을 고른 뒤에

10개의 순서쌍에 맞게 swap을 진행한 후 최대값을 계속해서 갱신해서 답을 찾습니다.

왜 시간 초과가 날까요?

10번 pick이면 10! = 대략 400만 아닌가요??..

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

string n;
int m, k, ans;
vector<pair<int, int> > pos; // swap할 수 있는 조합들을 저장

bool vis[10];
vector<pair<int, int> > picked;

void calc() {
	string num = n;
	for (int tc = 0; tc < picked.size(); tc++) {
		int i = picked[tc].first;
		int j = picked[tc].second;
		if (num[j] == '0') return;
		swap(num[i], num[j]);
	}
	ans = max(ans, stoi(num));
}

void dfs(int cnt) {
	if (cnt == k) {
		calc();
		return;
	}

	for (int i = 0; i < pos.size(); i++) {
		if (vis[i] == false) {
			vis[i] = true;
			picked.push_back(pos[i]);
			dfs(cnt + 1);
			picked.pop_back();
			vis[i] = false;
		}
	}
}


int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> k;
	m = n.size();
	ans = stoi(n);
	for (int i = 1; i <= m; i++) {
		for (int j = i + 1; j <= m; j++) {
			pos.push_back({ i - 1, j - 1 });
		}
	}

	dfs(0);

	cout << ans << '\n';
	return 0;
}

zigui 2년 전 1

pos 크기가 n이 6자리일 때 (6+1)*6/2 = 21이기 때문에 21*20*19*18*17*16*15*14*13*12만큼 연산이 수행됩니다.

paparoni 2년 전 0

@zigui
다시 보니까 확실히 터질 만 했네요. 시간 내주셔서 답변 감사합니다.

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

문제

문제

출처

ICPC

시간 초과가 나는 이유

paparoni 2년 전 0

zigui 2년 전 1

paparoni 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말