백준 1039 교환 혼내주기

 

 

brute force 문제.
처음에 방문 체크를 위해

int cache[1000005][11];

 

 

이런 배열을 선언하고 stoi로 확인했는데, 고수들의 풀이를 보니 set이나 map을 사용했길래 또 한 수 배웠다. 특히 이 문제 같은 경우는 나올 수 있는 경우의 수가 6!밖에 안되기 때문에 메모리를 왕창 아낄 수 있다.

오늘의 교훈: dp는 map hashmap으로도 할 수 있다.

 

 

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

set<string> cache[11];
int n, m, k, ans = 0;
bool able = false;

void input() {
    fastio;
    cin >> n >> k;
}

void d(string& num, int _cnt) {
    if(_cnt == 0) {
        ans = max(ans, stoi(num));
        able = true;
        return ;
    }

    auto it = cache[_cnt].find(num);
    if(it != cache[_cnt].end()) return ;
    cache[_cnt].insert(num);
    
    for(int i = 0; i < m; ++i) {
        for(int j = i+1; j < m; ++j) {
            if(num[j] == '0' && i == 0) continue;
            swap(num[i], num[j]);
            d(num, _cnt-1);
            swap(num[i], num[j]);
        }
    }
}

int main() {
    input();
    string num = to_string(n);
    m = num.size();

    d(num, k);
    cout << (able ? ans : -1);
}