1039: 교환

• toc {:toc}

문제 확인하기

1039: 교환 문제 확인하기

풀이

연산 자체는 i와 j를 골라 swap하는 간단한 연산이다. 다음의 연산을 K번 진행하여 나올 수 있는 최댓값을 구하는 문제이다. 이때, 집중해서 봐야할 점은 K번을 진행한다는 부분이다.

• 주어진 연산을 K번 했을 때, 만들 수 있는 가장 큰 수
  1. 1~K번 연산을 진행 중 나올 수 있는 가장 큰 수
  2. K번째 연산을 했을 때 나올 수 있는 경우의 수에서 가장 큰 수

다음 1, 2번 중 어떤 것을 의미할까? 해당 문제는 2번을 의미한다. 때문에 K번의 연산을 반드시 진행해야 하므로 level을 통해 해당 계산이 몇 번 연산됐는지 확인한다. 모든 경우의 수를 확인해야 하기에 BFS를 사용하고 방문했을 경우 방문 여부를 체크한다. 이후 K번 연산한 것을 따로 max_q에 저장해놓고 max_q에서 가장 큰 수를 반환한다.

#include <bits/stdc++.h>
using namespace std;
 
int depth[1000001];
int visit[1000001] = {};
string N;
int res = 0, K, level=0;
queue<pair<string, int>> q;
queue<int> max_q;
 
string Swap(string str, int i, int j){
    char temp;
    temp = str[i];
    str[i] = str[j];
    str[j] = temp;
    return str;
}
 
 
void bfs(){
    int stage = 0;
    while(q.empty()==0){
        string str = q.front().first;
        level = q.front().second;
        if (stage != level) {
            stage = level;
            fill(visit, visit+1000001, 0);
        }
        if (level == K) {
            max_q.push(stoi(str));
            q.pop();
            continue;
        }
 
        for(int i=0; i<N.size()-1; i++){
            for(int j=i+1; j<N.size(); j++){
                string change = str;
                if(i==0 && str[j] == '0') continue;
                change = Swap(str, i, j);
 
                int val = stoi(change);
                // 방문 여부 확인
                if (!visit[val]){
                    visit[val] = 1;
                    q.push({change, level+1});
                }                 
            }
        }
        q.pop();
    }
}
 
int main(){
    ios::sync_with_stdio(true);
    cin.tie(0); cout.tie(0);
    
    cin >> N >> K;
 
    q.push({N, 0});
 
    if (K==0){
        cout << N << endl;
        exit(0);
    }
    else if (N.size() == 1 || (N.size() == 2 && stoi(N) % 10 == 0)){
        cout << -1 << endl;
        exit(0);
    }
 
    bfs();
 
    while(!max_q.empty()){
        if(res < max_q.front()){
            res = max_q.front();
        }
        max_q.pop();
    }
 
    cout << res << endl;
 
 
    return 0;
}

참고문헌

연결문서