[백준알고리즘] 1039번: 교환 -C++

[백준알고리즘] 1039번: 교환 -C++

1039번: 교환 (acmicpc.net)

1039번: 교환

굉장히 어려웠다.

 

풀고 제출을 했었는데 틀렸다고 나왔고 해당 문제가 뭔지 알았는데, 고치지 못했다. 결국 다른 분의 블로그를 참고해서 문제를 푸는 법을 알았고, 이해한 내용을 바탕으로 다른 내용으로 풀고 싶었다.

아래 블로그의 얍문님의 포스팅을 보고 BFS로 푸는 방법에 대해서 알게 됐다.

[ 백준 1039 ] 교환 (C++) :: 얍문's Coding World.. (tistory.com)

[ 백준 1039 ] 교환 (C++)

 

그리고 이해한 내용을 바탕으로 DFS도 가능할 것 같아서 시도했고, 통과했다. 이후 DFS 코드를 찾아보다가 찬쿤님의 블로그를 보게 됐는데 코드가 똑같다고 봐야 돼서 같이 첨부한다.

백준 1039번 : 교환 (c++) :: 찬쿤 (tistory.com)

백준 1039번 : 교환 (c++)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

 

---

 

먼저, 통과하기 전에 실패했을 때에는 삽입정렬과 같이 진행을 했다. 수를 하나씩 읽어가면서 가장 큰 수를 만들었다. 그리고, 모두 비오름차순으로 만든 뒤에는 맨 뒤의 두 숫자만 위치를 바꾸도록 했다.

 

예를 들어서, \( 312 \)라는 수가 있다면, \( 321 , 312 , 321 ... \) 이런 식으로 반복했다.

 

이게 가장 작은 수가 나오는 경우라고 생각했고, 만약 \( 0 \)이 이 숫자열에 있다고 하더라도, 맨 뒤로 옮겨질 것이기 때문에 괜찮을 것이라고 생각했다.

 

예를 들어서, \( 100 \)라는 수가 있다면, \( 100, 100, 100 ... \)이 반복될 것이기 때문이다.

 

하지만, 내가 예상하지 못하는 문제가 있었다. 중간에 중복되는 수가 존재하는 경우다. 이 경우에는 끝의 두 자리를 바꾸는 게 가장 최댓값이 되는 게 아니다.

 

예를 들어서, \( 54432 \)라는 수가 있다면, 두개의 자릿수에 위치한 수를 서로 자리 바꿨을 때 가장 큰 수는 \( 54432 \)가 그대로 나와야지, \( 54423 \)이 아니기 때문이다.

 

이러한 문제가 있었고, 단순히 visit을 사용하는 것은 \( 321 , 312 , 321 ... \) 와 같이 반복되는 수들을 체크할 수 없다고 생각했다. 또한, 매번 가장 큰 자릿수의 숫자부터 삽입 정렬을 위한 탐색을 하는 것도 옳지 않은 정렬법이기 때문에 애를 먹었다.

 

---

 

그러다가 얍문님의 블로그를 보게 되었고, BFS를 통해서 각 depth마다 visit을 만들어주는 정도로 반복을 최소화하는 것을 알게 되었다.

 

그리고, 그리디한 방법으로는 다음 단계에서의 최댓값을 보장하지 못한다는 것을 알고는 있었는데, 적용을 하지 못하고 있었기 때문에 BFS, DFS를 생각하지 못했었다. 하지만 포스팅을 통해 각 단계마다 최댓값이 아니더라도, 다음 단계에서 최댓값을 만들 수 있기 때문에 계속해서 사용해서 모든 경우의 수를 확인하는 방법도 해결된다는 것을 알았다.

 

이렇게 이해한 내용을 바탕으로 BFS로 푸신 코드의 개념을 DFS로 가져왔다. DFS로 풀 때도 BFS의 각 depth마다 거쳤던 것과 마찬가지 2중 for문의 과정을 거친다. 그렇게 각 노드마다 루트노드가 되어 서브 트리에서 swap을 한 값들 중에서 가장 큰 값을 가져오게 했다.

그렇게 해서 최종적으로 K번의 swap을 거쳐 가장 큰 수가 나오게 된다.

 

아래는 그러한 방법으로 푼 C++ 코드다. 다 풀고 나니까 위에서 말했듯이 찬쿤님의 코드와 같았다.

#include <iostream>
#include <cstring>
#include <string>

int nextMaximum[1000001][11];

void solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false); 
	std::cin.tie(NULL); 
	std::cout.tie(NULL); 
	
	solve();
}

int dfs(std::string num, int depth)
{
	if (0 == depth)
		return stoi(num);

	const int currNum = stoi(num);
	int& maximum = nextMaximum[currNum][depth];

	if (0 <= maximum)
		return maximum;

	for (int i = 0; i < num.length(); i++)
	{
		for (int j = i + 1; j < num.length(); j++)
		{
			if (0 == i && '0' == num[j]) 
				continue;

			std::swap(num[i], num[j]);
			maximum = std::max(maximum, dfs(num, depth - 1));
			std::swap(num[i], num[j]);
		}
	}

	return maximum;
}

void solve(void)
{
	std::string n;
	int k;
	std::cin >> n >> k;
	
	memset(nextMaximum, -1, sizeof(int) * 1000001 * 11);

	std::cout << dfs(n, k);
}