[BOJ-1039] 교환(C++)

백준 1039 교환

 

1039번: 교환

 

문제 설명

 

 - 0으로 시작하지 않는 정수 N이 주어진다.

 

 - M을 정수 N의 자릿수라 할 때, 1<= i < j <= M 인 i와 j를 위치 숫자를 바꾸는 연산을 K번 한다.

   ex) 1234가 있을 때 i=1, j=4인 경우 위치 변경 연산을 1번 하게 되며, 4231이 된다.

 

 - 바꾼 수가 0으로 시작하면 안된다.

 

 - 연산을 K번 하여 나올 수 있는 최댓값을 구하라.

   만약 연산을 K번 할 수 없으면 -1을 출력하라.

---

 

입력 값

 

 - 첫째 줄에 정수 N과 K가 주어진다.

 

 - N은 100만보다 작거나 같은 자연수이다.

 

 - K는 10보다 작거 같은 자연수이다.

 

---

 

 

예제

 

---

 

 

문제 분석

 

 - 이 문제는 i번째 위치와 j번째 위치를 K번 바꾼 숫자 중 가장 큰 값을 출력하는 문제이다.

 

 - 즉, K번 연산을 모두 하고 나서 그 중 가장 큰 값을 찾으면 된다.

 

 - 단순하게 생각해보자. 정수 N은 100만이하의 자연수이다. N이 100만인 경우 답은 무조건 100만이기 때문에 

   정수 N은 6자리 숫자일 떄 최대 경우의 수를 가질 것이다.

 

 - N이 6자리 자연수라고 가정하면

   i=1일때 j는 2~6이 가능하다. 즉 5가지 경우가 나온다.

   i=2일때 j는 3~6이 가능하다. 즉 4가지 경우가 나온다.

   i=3일때 j는 4~6이 가능하다. 즉 3가지 경우가 나온다.

   i=4일때 j는 5~6이 가능하다. 즉 2가지 경우가 나온다.

   i=5일때 j는 6~6이 가능하다. 즉 1가지 경우가 나온다.

   i=6일때 j는 가능한 수가 없다. 즉 0가지 경우가 나온다.

   결론적으로, 한 번의 교환 연산을 할 수 있는 경우의 수는 15가지이다.

 

 - K는 10이하의 자연수이기 때문에 15^10 = 576650390625가 된다.

   즉, 단순한 방법으로는 시간안에 불가능하다.

 

 - 이때 사용하는 방법이 메모이제이션이다.

 

 - 이 문제에서 위치 변경에 의해 어떠한 숫자가 나왔을 때 그 숫자가 전에 나왔다면 다시 계산할 필요가 없는 것이다.

   ex) 3번의 위치 변경에 의해 123이라는 숫자가 나왔고, 5번의 위치 변경에 의해 다시 123이 나왔다면

        5번 이후의 변경은 3번에서 이미 했던 연산을 반복하게 되기 때문에 계산할 필요가 없어지는 것이다.

 

 - 여기서 중요한 것은, 위치 변경 연산을 홀수의 경우, 짝수의 경우로 나눠서 생각해야 한다는 것이다.

   같은 숫자가 나오더라도, 위치 변경 연산이 홀수인 경우와 짝수인 경우 결과가 달라지기 때문이다.

   왜냐하면, 짝수의 연산으로 같은 값을 만들 수 있지만, 홀수의 연산으로는 같은 값을 만들 수 없기 때문이다.

   ex) 1234라는 숫자를 2번 바꾸면 (1234 -> 2134 -> 1234) 같은 값을 만들 수 있지만,

        1234라는 숫자를 3번 바꿔서 1234를 다시 만들 수 없기 떄문이다.

 

 - 즉, 3번 연산하여 123이 나온것과 5번 연산하여 123이 나온 것은 다시 계산할 필요가 없지만,

   3번 연산하여 123이 나오고, 4번 연산하여 123이 나왔다면 다시 계산을 해야 한다는 것이다.

 

 - 결론적으로, 이 문제는 bfs를 이용하여 0에서부터 K번까지 모든 연산을 살펴보면서, 

   홀수, 짝수 나누어서 반복 계산을 하지 않도록 하여 모든 경우를 살펴보는 문제이다.

 

 - 또 주의할 점은 연산을 할 때 0으로 시작할 수 없다는 조건을 생각해야 한다는 것이다.

 

 - 여기서 시간복잡도는 모든 수를 살펴보기 때문에 O(2N) = O(N) 임을 알 수 있다.

   (대략적으로 200만의 연산을 하게 된다.) 

---

 

소스 코드

#include <bits/stdc++.h>

using namespace std;

int N, K;

int numSize;

int modK;

bool visited[2][1000001];

// 초기값을 -1로 설정한다.
// K번 연산을 한 경우만 값을 비교하여 갱신한다.
int result = -1;

void swapNumber(string& number, int i, int j) {
	char tmp = number[i];
	number[i] = number[j];
	number[j] = tmp;
}



int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> K;

	modK = K % 2;


	numSize = to_string(N).size();

	// bfs
	queue<pair<string,int>> q;
	q.push({ to_string(N),0 });

	while (!q.empty()) {
		string nowNumber = q.front().first;
		int cnt = q.front().second;

		q.pop();

		// bfs를 이용하기 때문에 K번 연산이 나온다면,
        // 뒷 부분도 최소 k번이기 때문에 더 이상 연산할 필요가 없다.
		if (cnt == K) {
			break;
		}

		int modCnt = (cnt + 1) % 2;

		// i랑 j고르기
		for (int i = 0; i < numSize; i++) {
			for (int j = i + 1; j < numSize; j++) {

				if (i == 0 && nowNumber[j] == '0') {
					continue;
				}

				swapNumber(nowNumber,i, j);
				int nowNumberInt = stoi(nowNumber);
				
                // 전에 연산하지 않은 경우
				if (!visited[modCnt][nowNumberInt]) {
					visited[modCnt][nowNumberInt] = true;
					q.push({ nowNumber,cnt + 1 });

				}
				swapNumber(nowNumber, i, j);

			}
		}
	}

	// K가 홀, 짝인지 확인 후 해당 값이 있는지 확인
	for (int i = 1; i < 1000001; i++) {
		if (visited[modK][i]) {
			result = max(result, i);
		}
	}

	cout << result << endl;
	

	return 0;
}