글 읽기 - 반례를 찾지 못하겠습니다

cgin 4년 전 0

- 제가 파악한 input 정보로는 1~N 개의 숫자들로 이루어진 수열들 중에서 1~N개의 숫자들 위치를 찾아내는 것으로 파악하였습니다.

- DFS 재귀를 첫번째 Index부터 시작해서 넣고 빼고 완전탐색으로 구현하였습니다.

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

using namespace std;

int max_length = 0;
int n;
vector<int> v;
string input;
bool visited[101];

void dfs(int index, int length) {
	if (length == n) {
		for (int i = 0; i < v.size(); i++)
			cout << v[i] << " ";
		cout << "\n";
		exit(0);
	}

	if (index > max_length)
		return;
	string temp = "";
	int temp_int = 0;
	for (int i = index; i <= index + 1; i++) {
		if (i > max_length)
			continue;
		temp += input[i];
		temp_int = stoi(temp);

		if (temp_int > n)
			continue;

		if (visited[temp_int] == true)
			continue;

		v.push_back(temp_int);
		visited[temp_int] = true;
		dfs(i + 1, length + 1);
		visited[temp_int] = false;
		v.pop_back();
	}


}
int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);

	cin >> input;

	max_length=input.size();
	int temp = max_length;
	n = 0;
	if (temp <= 9)
		n = temp;
	else {
		n += 9;
		temp -= 9;
		n += (temp / 2);
	}

	dfs(0, 0);

	return 0;
}

ghkdiwl 3년 전 0

12345678910

옛날 질문이지만 제 반례랑 같은거라 답달고 갑니다. 언젠간 누가보겠죠.

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

문제

문제

출처

ICPC

반례를 찾지 못하겠습니다

cgin 4년 전 0

ghkdiwl 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말