[Algorithm][DFS] 1244. [S/W 문제해결 응용] 2일차 - 최대 상금

순서

I. 문제

II. 접근

III. 구현

문제출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15Khn6AN0CFAYD&categoryId=AV15Khn6AN0CFAYD&categoryType=CODE&problemTitle=1244&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

---

I. 문제

숫자를 n 자리 준다 (ex 3 4 5 7 8)
교환 기회를 준다 ( ex 3 )

교환 기회만큼 숫자의 각 자리수를 교체할 수 있다.
34578 -> 43578 (3,4교체) -> 83574 (4,8 교체) -> 87534 (3,7 교체)

반드시 교환 기회를 다 써야 숫자가 완성된다고 할 때, 완성된 숫자 중 최대 값을 구하시오.

입력형식 가장 첫 줄은 전체 테스트 케이스의 수이다. 최대 10개의 테스트 케이스가 표준 입력을 통하여 주어진다. 각 테스트 케이스에는 숫자판의 정보와 교환 횟수가 주어진다. 숫자판의 정보는 정수형 숫자로 주어지고 최대 자릿수는 6자리,  최대 교환 횟수는 10번이다.	출력형식 각 테스트 케이스마다, 첫 줄에는 “#C”를 출력해야 하는데 C는 케이스 번호이다. 같은 줄에 빈 칸을 하나 사이에 두고 교환 후 받을 수 있는 가장 큰 금액을 출력한다.
10 123 1 2737 1 757148 1 78466 2 32888 2 777770 5 436659 2 431159 7 112233 3 456789 10	#1 321 #2 7732 #3 857147 #4 87664 #5 88832 #6 777770 #7 966354 #8 954311 #9 332211 #10 987645

 

---

II.접근

 

1. 입력

숫자는 std::string으로 받고 알고리즘도 std::string으로 처리해주지만
최종 답안만 int로 변환시킨다.

2. 문제 풀이

전체탐색을 진행한다 BFS, DFS 모두 가능하지만 전형적인 DFS가 떠오르는 문제

2중 for문으로 모든 경우의 교환을 전체 탐색하여 최댓값을 정해준다.
-> 전형적인 DFS문제는 가지치기가 중요하다.

 

---

3. 구현

 

<hide/>
#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;

int T{ 0 }; // 테스트케이스
int start_chance{ 0 }; // 찬스수
int len{ 0 }; // 숫자길이
int ans{ 0 }; // 정답
int flg_exit{ 0 }; // 예외처리용 탈출 플래그
string start_number; // 시작

void input() {
	start_number = "";
	start_chance = 0;
	len = 0;
	ans = 0;
	flg_exit = 0;
	cin >> start_number >> start_chance;
	len = start_number.length();
}

// 숫자변경 함수로 따로 만들어둠.
std::string changeNum(const string number, int i, int j) {
	string ret;
	ret = number;
	ret[j] = number[i];
	ret[i] = number[j];

	return ret;
}

// 메인 알고리즘
void DFS(string number, int chanceleft) {
	int flg_issame = 0;
	if (flg_exit) {
		return;
	}
    
    // 정상적인 경우 (탐색 제일 깊을 때) 탈출
	if (chanceleft <= 0) {
		if (std::stoi(number) >= ans) {
			ans = std::stoi(number);
		}
		return;
	}
    
    //예외처리 탈출**
    // 현재 가장 큰 수로 정렬이 되어있다면, 남은 찬수 파악해 탈출
	for (int i = 1; i<int(number.size()); i++) {
		if (number[i - 1] < number[i]) {
			break;
		}
		else {
			if (number[i - 1] == number[i]) {
				flg_issame = 1;
			}
			// 모두 정렬이 되어있다면
			if (i == int(number.size()) - 1) {
				// 짝수 개 남았을 때
				if (!(chanceleft % 2)) {
					ans = stoi(number);
				}
				// 홀수 개 남았을 때
				else {
					if (flg_issame) {
						ans = stoi(number);
					}
					else {
						ans = stoi(changeNum(number, i - 1, i));
					}
					flg_exit = 1;
					return;
				}
			}
		}
	}
    
    //DFS 기본 알고리즘
	for (int i = 0; i < len; i++) {
		for (int j = i + 1; j < len; j++) {
			int extflg = 0;
			string nextnum;
			nextnum = changeNum(number, i, j);
			DFS(nextnum, chanceleft - 1);
		}
	}
}

int main() {
	cin >> T;

	for (int i = 0; i < T; i++) {
		input();
		DFS(start_number,start_chance);
		printf("#%d %d\n", i + 1, ans);
	}
	return 0;
}

 

예외처리 생각들

1. 동일한 숫자를 변경했을 때?
2. A->B->A 식의 변경이 이루어졌을 때?
3. B->A->A 식의 변경이 이루어졌을 때?

다 구현해보고 고민해봤는데 결국 예외가 있었고 최종적으로
이미 해당 숫자의 조합에서 가능한 최대값으로 정렬이 되었을 때가 중요했다.
(ex 615724의 조합에서 최대 = 765421)