1244. 최대 상금

링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15Khn6AN0CFAYD 

SW Expert Academy

 

분류

완전 탐색

 

개인적 난이도

매우 쉬움

쉬움

보통

어려움

매우 어려움

 

핵심 알고리즘

완전 탐색을 이용해 바꿀 수 있는 모든 경우의수를 고려한다.

Combination(6, 2) ^ 10의 값이 5.77 E+11 로 매우 크기 때문에 cache를 사용하였다.

 

시행착오

완전탐색보다 더 효율적인 알고리즘이 있지 않을까 라는 생각에

많은 고민을 했지만 최대 자릿수는 6자리, 최대 교환 횟수는 10회로 제한되어 있었기 때문에 완전탐색으로 해결하였다.

코드

#include<iostream>
#include<map>

using namespace std;

int len;
map<int, int> cache;

int swap(int N, int x, int y){
	int vx, vy, mx = 1, my = 1;
	for (int i = 1; i < x; i++) mx *= 10;
	for (int i = 1; i < y; i++) my *= 10;
	vx = (N / mx) % 10;
	vy = (N / my) % 10;

	return N - vx * mx - vy * my + vx * my + vy * mx;
}

int solve(int N, int cnt){
	if (cache.find(N * 100 + cnt) != cache.end()) return cache.at(N * 100 + cnt);
	if (!cnt) return N;

	int max = -1;

	for (int i = 2; i <= len; i++){
		for (int j = 1; j < i; j++){
			int s = swap(N, i, j);
			s = solve(s, cnt - 1);
			max = (max < s)?s:max;
		}
	}

	cache[N * 100 + cnt] = max;

	cnt--;
	return max;
}

int main(int argc, char** argv){
    int tc, T;
    scanf("%d", &T);

    for (tc = 1; tc <= T; ++tc)
    {
        int N, cnt;
		scanf("%d %d", &N ,&cnt);

		cache.clear();
        int i = N;
		len = 0;
		while (i > 0){
			len++;
			i /= 10;
		}

		printf("#%d %d\n", tc, solve(N, cnt));
    }

    return 0;
}