글 읽기 - BFS로 풀어야 하는 이유...

zhoang3 4년 전 0

숫자를 큰 순서대로 정렬하고

남은 K번은 그냥 뒤에 두개 바꿔주는 걸로

제일 먼저 생각나서 구현했었는데 왜 안되는 건가요..?

#include<iostream>
#include<string.h>
#include<algorithm>

using namespace std;

int N, K;
int len;
char Num[10];

void Switch(int start) {

	int idx = 0;
	pair<int, int> large = make_pair(0, 0);

	if (K == 0) return;

	if (start >= len) { // 정렬이 다하고 K가 남으면 뒤에 두자리만 계속 바꿔 주기
		idx = len - 2;
		large = make_pair((int)Num[len - 1] - 48, len - 1);
	}
	else {
		idx = start;

		for (int i = start; i < len; i++) { // 제일 큰수 찾기
			int n = (int)Num[i] - 48;
			if (large.first < n) large = make_pair(n, i);
		}

	}

	if (idx == 0 && large.first == '0') { // 0과 바꿔야 할 경우

	}
	else if (idx == large.second) { //이미 제일 큰 수가 앞에 위치하면

	}
	else { // 스왑
		char tmp = Num[idx];
		Num[idx] = (char)large.first + 48;
		Num[large.second] = tmp;

		K--;
	}
	
	Switch(start + 1);
}

int main() {
	cin >> N >> K;

	sprintf(Num, "%d", N); //숫자를 char 배열로 변환
	len = strlen(Num);

	if (len == 1 || (len == 2 && Num[len -1] == '0')) { // 문자길이가 1이거나 
		cout << -1 << endl;								// 2이면서 뒤에 0일때 -1 출력
		return 0;
	}

	Switch(0);

	cout << Num << endl;
}

chogahui05 4년 전 0

plz check this input

900 2

lch9502 2년 전 0

900 2
ans : 900

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

문제

문제

출처

ICPC

BFS로 풀어야 하는 이유...

zhoang3 4년 전 0

chogahui05 4년 전 0

lch9502 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

문제

문제

출처

ICPC

​BFS로 풀어야 하는 이유...​

zhoang3 4년 전 0

chogahui05 4년 전 0

lch9502 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

BFS로 풀어야 하는 이유...