(C++) - 백준(BOJ) 1039번 : 교환

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

1039번: 교환

brute force로 푼 문제였습니다.

 

풀이방법

 1. 이차원 배열 d를 다음과 같이 정의합니다. : d[n][k] => n이라는 수를 만들기 위해 사용한 움직임 개수 k에는 n이 저장됩니다.

 

 2. 재귀함수를 통해 i번째와 j번째를 모두 확인하면서 swap해봅니다. swap의 결과 가장 앞의 수가 '0'이라면 원복해줍니다. 모두 확인한 후에는 원래자리로 다시 swap합니다.

 

 3. 함수의 반환값을 출력합니다.

Code

#include <bits/stdc++.h>
using namespace std;
string n;
int k, ans;
int d[1000001][11];

int dfs(string num, int count){
    if(count == k) return stoi(num);
    int &ret = d[stoi(num)][count];
    if(ret != -1) return ret;

    for(int i = 0; i < n.size(); i++){
        for(int j = i + 1; j < n.size(); j++){
            swap(num[i],num[j]);
            if(num[0] == '0') {
                swap(num[i],num[j]);
                continue;
            }
            ret = max(ret,dfs(num,count+1));
            swap(num[i],num[j]);
        }
    }
    return ret;
}

int main(){
    cin >> n >> k;
    memset(d,-1,sizeof(d));
    cout << dfs(n,0);
}