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

cmychs 4년 전 0

2중 for문을 통하여 첫자리가 0으로 만들어지는 경우를 제외하고 모든 경우를 (방문 안했을 경우) 큐에 넣고 cnt가 k가 된 값들 중 가장 큰 값을 출력하게 했는데 게시판에 있는 값들은 모두 정상적으로 돌아갑니다!

다른 반례를 못찾겠습니다 ...

시작과 동시에 틀렸습니다가 나옵니다.

#include <iostream>
#include <queue>
#include <string>

#define max(a, b) a < b ? b : a

using namespace std;

int n, k, answer = -1, str_len;
bool visited[11][1000000];

int __strlen(char chr[]) {
	int ret = 0;
	while (chr[ret++] != '\0');
	return ret - 1;
}

void __swap(char &a, char &b) {
	char tmp = a; a = b; b = tmp;
}

int convert_num(char aa[]) {
	int ret = 0, ten_tmp = 1;
	int str_size = __strlen(aa);
	for (int i = str_size - 1; i >= 0; i--) {
		ret += (aa[i] - '0') * ten_tmp; ten_tmp *= 10;
	}
	return ret;
}

struct TMP {
	char chr[10]; int cnt, size;
	TMP(int cnt1, int size1, char chr1[]) {
		cnt = cnt1; size = size1;
		for (int i = 0; i <= size1; i++) {
			chr[i] = chr1[i];
		}
	}
};

int main(void) {
	ios::sync_with_stdio(0); cin.tie(nullptr);
	cin >> n >> k; 
	char tmp_char[10]; sprintf(tmp_char, "%d", n); str_len = __strlen(tmp_char);
	queue<TMP> q; q.push(TMP(0, str_len, tmp_char)); visited[0][n] = true;
	
	while (!q.empty()) {
		TMP cur = q.front(); q.pop();
		if (cur.cnt == k) {
			int tmp_num = convert_num(cur.chr);
			answer = max(answer, tmp_num); continue;
		}
		char tmp[10];
		for (int i = 0; i <= str_len; i++) tmp[i] = cur.chr[i];
		for (int i = 0; i < str_len; i++) {
			for (int j = i + 1; j < str_len; j++) {
				if (i == 0 && tmp[j] == '0') continue;
				__swap(tmp[i], tmp[j]);
				int tmp_num = convert_num(tmp);
				if (!visited[cur.cnt + 1][tmp_num]) {
					visited[cur.cnt + 1][tmp_num] = true; 
					q.push(TMP(cur.cnt + 1, str_len, tmp));
				}
				__swap(tmp[i], tmp[j]);
			}
		}
	}
	printf("%d\n", answer);
	return 0;
}

pichulia 4년 전 1

N은 1,000,000 이하인 자연수입니다.

cmychs 4년 전 0

엇.. 와 감사합니다 ㅜㅜ.. 이런 실수 줄여야 할텐데

정말 감사합니다.. 오늘은 답답했었는데 확 풀렸습니다!

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

문제

문제

출처

ICPC

반례를 못 찾겠습니다 ㅠ

cmychs 4년 전 0

pichulia 4년 전 1

cmychs 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말