백트래킹이란? 최대 상금 문제

백트래킹은 DFS 과정에서 불필요한 부분을 가지치기하는 과정을 의미한다.

 

SW expert 에서 최대 상금 문제를 풀다 정리하게 되었다.

사실상 내가 기존 학습한 카테고리에서는 DFS 보다는 재귀에서 활용하는 느낌. (DFS가 재귀니 거기서 거기지만) 

 

1) input으로 숫자 열이 주어지면 string으로 받아버리기.

이후 arr[i]로 접근하면 char형이 되기 때문에, string.substr(start, length)로 문자열 형식으로 자른 후 stoi()로 변환한다.

 

아니면 arr[i] - '0' 으로 캐릭터형을 숫자로 변환해주면 됨. 물론 char형이긴 함. int로 변환하거나 int와 계산 안에 넣어야  

 

2) 최대값을 찾는 알고리즘을 적용할 수 없고, 바꾸고 최대값을 찾는 이유.

바꾼후에 그 값이 바꾸기 전보다 작아져도, 반드시 교환 횟수를 소모해야하기 때문.

따라서 1대1 교환을 모두 진행해본 후, 그 중 가장 큰 값을 선택해서 다음 교환을 다시 진행해야 한다.

 

하지만 첫번째 교환에서 최대의 교환이었다고해서, 그 숫자를 바탕으로 두번째 교환이 최적이라는 보장은 없다.

32888 예시에서 한번만 교환한다면 82883 이 최선이 되겠지만, 두번이라면 88832로 3이 십의 자리로 가는게 최선이기  때문.

 

따라서 DFS처럼 한번의 교환이 트리구조 맨 자식노드까지 진행되어야 한다.

이때, 모든 교환을 DFS 끝까지 진행했다가는 너무 많은 계산 횟수가 존재하게 되기 때문에,

현재 숫자, 교환 횟수 두가지가 같은 계산결과를 저장해두는 방식으로 코딩한다.

 

이는 현재 숫자와, 남은 카운트 갯수를 기준으로 내 맘대로 해시 함수를 만들어서 unordered_map에 저장하고,

있는 경우를 제거해주는 방식으로 진행하였다.

 

코드는 다음과 같다.

 

#include<iostream>
#include<string>
#include<algorithm>
#include<unordered_map>

using namespace std;

int max_num = 0;
unordered_map<int, int> save_leaf;

int DFS(string num, int cnt) {
	if (cnt == 0) {
		max_num = max(stoi(num), max_num);
		return 0;
	}
	else if (save_leaf.find((stoi(num)+cnt)*(cnt+10)) != save_leaf.end()) {
		return 0;
	}
	else if (cnt > 0) {
		string temp_str = num;

		for (int i = 0; i < num.length()-1; i++) {
			for (int j = i + 1; j < num.length(); j++) {
				char temp = temp_str[i];
				temp_str[i] = temp_str[j];
				temp_str[j] = temp;
				
				//DFS이전에 있는 변화는 인자에서 변화를 주지 않는 한, 변화가 계속된다고.
				DFS(temp_str, cnt-1);

				//temp_str과 cnt-1 을 인자로 가지는 친구의 최대값은 max_num이라 할 수 있음,
				//temp_str과 cnt-1으로 hash를 만들어서 그 안에 max_num을 만들자.
				//(temp_str + (cnt-1))*10
				save_leaf.insert({ (stoi(temp_str) + cnt - 1) * (cnt - 1 + 10), 1 });

				//이후에 원래대로 초기화해야 된다고.
				temp = temp_str[i];
				temp_str[i] = temp_str[j];
				temp_str[j] = temp;
			}
		}
	}
}

int main(int argc, char** argv)
{
	int test_case;
	int T;
    
	cin >> T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	string num;
	int cnt;
	for (test_case = 1; test_case <= T; ++test_case)
	{
		max_num = 0;
		save_leaf.clear();

		cin >> num;
		cin >> cnt;
		
		DFS(num, cnt);
		
		cout << "#" << test_case << " " << max_num << "\n";
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

 

string을 교환하던 함수는 swap으로 교환해주면 된다.