[1244번] 최대 상금

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

완전탐색을 통해 모든 값을 다 찾아본다.

이때 visit라는 dp배열을 이용하는데 cnt & 1의 의미는

스왑할때마다 1 2 -> 2 1 -> 1 2가 되는데

2 1에서 cnt & 1 즉, 이전에 왔던 곳이면(홀,짝수로 보아) 

더 볼 필요가 없음을 의미한다.

소스 코드 : 

#include <iostream>
 
#define SWAP(a, b){int t = a; a = b; b = t;}
#define MAX(a,b)(a > b ? a : b)
int n;
int len;
int ans;
bool visit[1000000][2][11];
int visitCnt;
 
void init() {
    ans = len = 0;
    visitCnt++;
}
int _strlen(char *str) {
    len = 0;
    for (; str[len]; len++) {}
    return len;
}
void combi(char *str, int cnt) {
    int mul = 1;
    int val = 0;
    for (int i = len - 1; i >= 0; i--) {
        val = val + (str[i] - '0') * mul;
        mul *= 10;
    }
    if (cnt == n) {
        ans = MAX(ans, val);
        return;
    }
    if (visit[val][cnt & 1][visitCnt]) {
        return;
    }
    visit[val][cnt & 1][visitCnt] = true;
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            SWAP(str[i], str[j]);
            combi(str, cnt + 1);
            SWAP(str[i], str[j]);
        }
    }
 
}
int main() {
    freopen("input.txt", "r", stdin);
    int tCase;
    scanf("%d", &tCase);
 
    for (int tc = 1; tc <= tCase; tc++) {
        init();
        char str[10];
        scanf("%s %d", str, &n);
 
        len = _strlen(str);
        printf("%s %d\n", str, n);
        combi(str, 0);
 
        printf("#%d %d\n", tc, ans);
    }
 
    return 0;
}