교환 - 1039

//1039 - 교환
 
#include <iostream>
using namespace std;
 
int N, K;
int length;
int cache[11][1000001];
 
void init()
{
    cin >> N >> K;
    string s = to_string(N);
    length = s.size();
    for(int i = 0; i<=K; ++i)
        for(int j = 0; j<1000001; ++j)
            cache[i][j] = -2;
 
}
 
int max(int u, int v)
{
    if(v == -1) return -1;
    return (u > v ? u : v);
}
 
int dp(int tries, int n)
{
    if(tries == K) return n;
    int& ret = cache[tries][n];
    if(ret != -2)
        return ret;
    bool flag = true;
    for(int i = 0; i<length; ++i)
        for(int j = i+1; j<length; ++j)
        {
            string s = to_string(n);
            swap(s[i], s[j]);
            if(s[0] == '0') 
            {
                swap(s[i], s[j]);
                continue;
            }
            flag = false;
            n = stoi(s);
            ret = max(ret, dp(tries+1, n));
            swap(s[i], s[j]);
            n = stoi(s);
        }
 
    if(flag)
        return ret = -1;
    return ret;
}
 
int main()
{
    init();
    cout << dp(0, N);
}

 

 

 

 

 

 

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

1039번: 교환

 

 

 

 

 

 

교환

재귀함수를 이용한 dp를 사용해 해결했습니다.

C[u][v] : u번의 차례일때 숫자가 v일때, K번까지 작업을 완료했을때 최대값을 저장함