[백준]1039번 교환 - C/C++

https://www.acmicpc.net/problem/1039

1039번: 교환

문제

0으로 시작하지 않는 정수 N이 주어진다. 이때, M을 정수 N의 자릿수라고 했을 때, 다음과 같은 연산을 K번 수행한다.

1 ≤ i < j ≤ M인 i와 j를 고른다. 그 다음, i번 위치의 숫자와 j번 위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다.

위의 연산을 K번 했을 때, 나올 수 있는 수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제에 주어진 연산을 K번 했을 때, 만들 수 있는 가장 큰 수를 출력한다. 만약 연산을 K번 할 수 없으면 -1을 출력한다.

---

 

    짧고 명료한 문제이다. 이러한 숫자들 간의 교환을 하여 최댓값/최솟값을 찾는 문제는 그래프를 순회하며 전부 다 확인할 수밖에 없다.

    다만 숫자가 최대 7자리 이고 이 중 2개의 숫자의 위치를 바꿔 10번의 깊이까지 들어갈 수 있기 때문에 가지치기를 해주어야 한다. 그래서 dp 배열을 만들어 이미 똑같은 깊이에서 교환을 진행하였다면 하지 않는 방식으로 그래프 순회를 진행한다.

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
int k;
int dp[1000001][11];
string arr;

int dfs(string snum, int depth) {
	if (depth == 0)
		return stoi(snum);

	int num = stoi(snum);
	int& ret = dp[num][depth];

	if (ret >= 0) return ret;

	for (int i = 0; i < snum.length(); i++) {
		for (int j = i + 1; j < snum.length(); j++) {
			if (i == 0 && snum[j] == '0')
				continue;
			swap(snum[i], snum[j]);
			ret = max(ret, dfs(snum, depth - 1));
			swap(snum[i], snum[j]);
		}
	}
	return ret;
	
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> arr >> k;

	memset(dp, -1, sizeof(dp));
	cout << dfs(arr, k);
	return 0;
}

---

    이 문제에서 신기했던 점은 int ret로 선언하면 시간이 엄청나게 오래 걸리고 int& ret으로 선언하면 시간이 굉장히 짧게 걸린다는 것이다. 이 차이는 변수를 선언하고 값을 할당하는데에서 오는 차이인가 했지만 int& 변수 역시 변수를 선언하고 주소 값을 할당하는 시간이 걸리는데 왜 이러한 차이가 나타날까 의아함을 가지게 되었다.

    그래서 구글링을 하던 도중 https://www.acmicpc.net/board/view/7686

글 읽기 - &연산자와 속도에 관하여 질문입니다.

을 발견하게 되었다.

    그래서 ret 변수를 모두 dp[num][depth]로 바꾸어 아래의 코드로 위 코드를 고쳐보았다.

if (dp[num][depth] >= 0) return dp[num][depth];

	for (int i = 0; i < snum.length(); i++) {
		for (int j = i + 1; j < snum.length(); j++) {
			if (i == 0 && snum[j] == '0')
				continue;
			swap(snum[i], snum[j]);
			dp[num][depth] = max(dp[num][depth], dfs(snum, depth - 1));
			swap(snum[i], snum[j]);
		}
	}
	return dp[num][depth];

    이렇게 코드를 변경하였더니 실제로 시간이 매우 짧게 나왔다. visual studio와 백준의 컴파일러 모두 int& 연산자를 실제 값으로 치환되어 사용되는 것인가 보다.

    하지만 그럼에도 선언과 할당의 소요 시간에대해 의문이 있었는데 해당 글의 답변은 캐시 때문이라고 하였다. 캐시라고 생각을 하여도 결국 변수에 값을 복사를 해오던 주소 값을 참조하던 dp[num][depth]의 값이 캐시에 올라가는 것이라 차이가 없지 않을까라고 생각을 했지만 복사를 해오면 메모리를 더 사용하여 캐시가 부족해지는 것일까? 뭔가 내가 모르는 게 있는 것인가 싶다.

    dfs 문제를 한번 풀고 싶어서 간단해 보이는 문제를 선택했는데 배워가는게 있는 것 같다. 앞으로 재귀를 사용할 때는 변수에 값을 옮기기보다는 참조자를 사용해보도록 해야겠다. 그리고 참조자와 그냥 변수의 차이도 실험해 보아야겠다!