글 읽기 - 아.. 어렵네요 ㅠㅠ 뭘 잘못 푼건가요 반례좀 잡아주세요 ㅠㅠ

2468ab 6년 전 0

접근이 잘못 된건가요 ?? ㅠㅠ 반례좀 찾아 주시면 감사하겠습니다 ㅠㅠ

k 의 값이 10이 될수도 있지만 사실 숫자가 1000000을 제외하고는 최대 6자리임으로

5번만에 무조건 최대값을 찾을수 있다고 생각했습니다. 그렇다면 여기서

생각을 해본 결과 만약 최대값을 찾는다면 그 다음 할수 있는 수는 가장 작은 두값을 바꿔나가는 과정이라고 생각했습니다.

여기서 또 하나 생각 해볼것이 그렇다면 예를 들어 3번만에 최대값을 가졌다면 5번 7번 9번째에는 무조건 최대값이 결정되게 됩니다 하지만

4번째 6번째 8번째 10 번째는 과연 3번째 최대값을 통해 만들어지는가?

여기서 생각한것이 홀수 번째에서 최대값이 나오면서 짝수번째에 최대값이 나온다면 k 값에 관련없이 최대값이 결정

홀수 번째에서 최대값이 나오면서 짝수번째에 최대값이 나오지 않는다면 k가 홀수이면 최대 k 가 짝수이면 최대 바로하나전

이런 식으로 생각해 코드를 구현해 보았습니다.

그러면 15^6 정도 시간복잡도에 중간에 안하는 경우도 있어서 시간상은 문제가 안될거라고 생각했습니다.

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string number;
string max_1 = "";    // 최대값 !!
string max_2 = "";    // 최대값에서 마지막 가장 작은 두 값을 바꾼값. !!
int cnt[10];         
int m, k, ans[10];    // m = 숫자의 갯수 , k = 바꿀 횟수 , ans[10] 정답 후보
bool ok = false;      // k번에 최대값을 찾았는지
void change(string &number) // ans 와 number 값 비교후 ans 값 바꾸기
{
	bool c = false;
	for (int i = 0; i < m; i++) {
		if (ans[i] == number[i] - '0') {
			continue;
		}
		if (ans[i] < number[i] - '0') {
			c = true;
			continue;
		}
		break;
	}
	if (c == true) {
		for (int i = 0; i < m; i++) {
			ans[i] = number[i] - '0';
		}
	}
	return;
}
void go(int cnt)                    
{
	if (ok == true || number[0] == '0' || cnt == 6) { // ok == true 최대값이 이미 결정된 상황
		return;                                       // number[0] == '0' 문제 조건 처음수 0이면 x
	}                                                 // cnt == 6 더이상 할 필요 x
	if (number == max_1) {                            // 숫자가 최대값일 경우
		if (cnt % 2 == k % 2) {                       // 홀짝인지 판단 둘다 홀홀 짝짝이면
			change(max_1);                            // 최대값을 찾음 -> ok = true;
			ok = true;                                // ans 값 체인지
		}
		else {
			change(max_2);                            // 홀짝, 짝홀 이면 max_2 
		}
		return;
	}
	if (cnt == k) {                                   // cnt == k 이면 ans값 change
		change(number);
		return;
	}
	for (int i = 0; i < m - 1; i++) {               // 모든 경우의수 해보자
		for (int j = i + 1; j < m; j++) {
			swap(number[i], number[j]);             
			go(cnt + 1);
			swap(number[i], number[j]);
		}
	}
}
int main(void)
{
	cin >> number >> k;
	m = number.size();
	if (m == 1) {                 // 1자리 숫자라면 -1 출력
		cout << "-1";
	}
	else if (m == 7) {            // 1000000 이라면 1000000 출력
		cout << "1000000\n";
	}
	else {                        // 나머지 경우
		for (int i = 0; i < m; i++) {
			cnt[number[i] - '0']++;
		}
		for (int i = 0; i < m; i++) {
			for (int j = 9; j >= 0; j--) {
				if (cnt[j] >= 1) {
					max_1.push_back(j + '0');   // 최대값 찾기
					cnt[j]--;
					break;
				}
			}
		}
		max_2 = max_1;                         
		swap(max_2[m - 2], max_2[m - 1]);     // 최대값 바로 전 값 
		go(0);                                // 재귀함수 고고
		if (ans[0] == 0) {                    
			cout << "-1\n";
		}
		else {
			for (int i = 0; i < m; i++) {
				cout << ans[i];
			}
			cout << '\n';
		}
	}
}

2468ab 6년 전 0

자문자답 합니다 ㅋㅋㅋㅋ

36번째줄

if (number == max_1 && cnt != 0)

으로 바꾸고 두자리수 처리 따로 해주면 맞네요 ㅠㅠ

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