1244번 최대상금 - [S/W 문제해결 응용]

1244번 최대상금 - [S/W 문제해결 응용]

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

 

이 문제는 이중 for문으로 완전탐색을 아주 그냥 돌려버렸다.

중복체크 안하고 돌리면 테스트케이스 7번까지는 돌아간다.

하지만 테스트케이스 8번부터 시간초과가 나버린다.

그러므로 중복체크 해야하므니다.

 

소스코드

 
xxxxxxxxxx
// 1244 최대상금 - 완탐
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
​
int T, seq;
vector<int> v;
int max_price;
int check[1000000][11];
​
int calc()
{
    int tmp = 0;
    for (int i = 0; i < v.size(); i++)
        tmp += (v[i] * pow(10, v.size() - i - 1));
    
    return tmp;
}
​
void swap(int f,int s)
{
    int first = v[f];
    int second = v[s];
    v[f] = second, v[s] = first;
}
​
void DFS(int n)
{
    if (n >= seq)
    {
        max_price = max(max_price, calc());
        return;
    }
​
    if (check[calc()][n]) return;       // 이 두줄이 중복체크용
    check[calc()][n] = 1;
​
    for (int i = 0; i < v.size(); i++)
    {
        for (int j = i+1; j < v.size(); j++)
        {
            swap(i, j);
            DFS(n + 1);
            swap(i, j);
        }
    }
}
​
void input()
{
    cin >> T;
    for (int i = 1; i <= T; i++)
    {
        string tmp;
        cin >> tmp >> seq;
        for (int j = 0; j < tmp.size(); j++)
            v.push_back(tmp[j] - '0');
        DFS(0);
        cout << "#" << i << " " << max_price;
        max_price = 0;
        v.clear();
    }
}
​
int main()
{
    input();
    
    return 0;
}