[SWEA 1244] 최대 상금

문제 링크

SWEA 1244

SW Expert Academy

 

---

아이디어

- 전체에서 가장 큰 숫자를 맨 앞자리로 가져오는식으로 그리디라고 생각할 수 있지만

  단순히 이런식으로 접근하면 아래의 두 케이스에서 8832라는 답을 동시에 낼 수 없다

  2

  3288 2

  2388 2

  따라서 그리디하게 접근 할 시 이것저것 복잡하게 조건을 따져야 할 것 같으므로

 

- 머리를 비우고 백트래킹으로 완전탐색을 하며 dp로 pruning을 하자

 

- visit[num][th] : th번 바꾸어서 상금이 num인 상태로 정의하자

  그래서 이미 방문 했다면 이후의 값들은 이미 이전에 계산했을테니 재귀를 빠져나간다.

---

소스코드

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

string ans;
bool visit[1000000][11];

void solve(string& s, int th, int chance)
{
    if (th == chance) {
        ans = max(ans, s);
        return;
    }

    int num = s[0]-'0';
    for (int i = 1; i < s.size(); ++i) {
        num *= 10;
        num += (s[i]-'0');
    }

    if (visit[num][th]) return;

    visit[num][th] = true;
    for (int i = 0; i < s.size() - 1; ++i) {
        for (int j = i + 1; j < s.size(); ++j) {
            std::swap(s[i], s[j]);
            solve(s, th + 1, chance);
            std::swap(s[i], s[j]);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);

    int t; cin >> t;
    for (int tc = 1; tc <= t; ++tc) {
        int chance;
        string str;
        cin >> str >> chance;

        ans = "0";
        memset(visit, 0, sizeof(visit));

        solve(str, 0, chance);
        cout << "#" << tc << ' ' << ans << '\n';
    }
    return 0;
}

 

 

 

공부한 것을 정리하기 위한 기록입니다.

틀린 부분이 있다면 부드럽게 알려주세요.