1. dfs 에서도 visit 를 사용합니다. 여기서 어떻게 사용하냐면, depth 에 따른 변동 값을 넣어줍니다. 오께이. 이정도 교환했는데, 그 값에 대해서 값이 정해져 있지 않으면, 반복하는 것이 상당히 많으므로, 그것을 넣어줘서 풀이합니다. dfs 에서도 visit 를 잘 사용하도록 해야 합니다. 어떤 값을 넣어서 중복을 피하게 할 수 있을지 고민하면 됩니다. 알고리즘은 맞는데 시간초과 나면 중복하는 것을 변경하면 됩니다. 메모리는 항상 넉넉함으로, 메모리 초과는 본적이 없으므로. |
/* 1244 최대상금 문제 13:53 에 풀어보도록 하겠습니다. 정해진 횟수만큼 교환이 끝나면 숫자판의 위치에 부여된 가중치에 의해 상금을 받습니다. 중복 교환 가능합니다. 입력을 받고, 정해진 만큼 교환을 실시해서 최대 상금을 받을 수 있도록 합니다. 가지치기만 주의하면 되겠습니다. */ #include <iostream> #include <algorithm> #include <string> using namespace std; #define SIZE 6 int map[SIZE]; int visit[11][1000000]; int maxVal; string num; int k; int length; int res; void problemIn() { cin >> num; cin >> k; length = num.size(); for (int i = 0; i < length; i++) { map[i] = num[i] - '0'; } } void init() { maxVal = 0; } /* 바꾸려는 수가 더 커야 바꿉니다를 넣어줘야 합니다. */ void dfs(int depth) { if (depth == k) { maxVal = max(maxVal, res); return; } for (int i = 0; i < length; i++) { for (int j = i+1; j < length; j++) { if (map[j] < map[i]) continue; swap(map[i], map[j]); res = 0; for (int i = 0; i < length; i++) { res += pow(10, length - 1 - i)*map[i]; } if (!visit[depth][res]) { visit[depth][res] = 1; dfs(depth + 1); } swap(map[i], map[j]); } } } void solve() { dfs(0); } int main() { int T; cin >> T; for (int tc = 1; tc <= T; tc++) { problemIn(); solve(); cout << "#" << tc << " " << maxVal << endl; init(); } return 0; } |