백준 1039 교환 (c++) : 피너클

https://www.acmicpc.net/problem/1039

1039번: 교환

dp를 이용해 푼 문제다.

string str;
string sam;
int cache[1000001][11];
int k;

str은 입력받는 문자열, sam은 중간중간 바뀌는 문자열이다.

cache는 dp에서 사용하는 저장공간이며 k는 바꾸는 횟수다.

int solve(string s, int num) {
	if (num == k) return stoi(s);
	int &ret = cache[stoi(s)][num];
	if (ret != -1) return ret;
	int ans = -1;

string s는 현재까지 바뀐 문자열이고 num은 현재까지 바뀐 횟수이다.

만약 num이 k와 같다면 그대로 s를 int로 바꿔 반환한다.

int &ret에는 cache에서 가져온 정보를 저장한다.

만약 ret이 -1이 아니라면, 즉 ret에 이미 정보가 저장되어 있다면 그 정보를 반환한다.

그후 정답을 나타낼 변수 ans에 미리 -1을 집어넣어놓는다.

	for (int i = 0; i < s.length(); i++) {
		for (int j = i + 1; j < s.length(); j++) {
			if (i == 0 && s[j] == '0') continue;
			sam = s;
			swap(sam[i], sam[j]);
			ans = max(solve(sam, num + 1), ans);
		}
	}

	return ret = ans;
}

 

for문을 통해 전달받은 s로 만들수 있는 모든 수열을 만든다.

만약 i가 0이고 s[j]가 '0'이라면, 즉 문자열 맨 앞에 0이 들어가게 된다면 continue를 통해 뒤의 명령들을 무시한다.

sam에 s를 집어넣고 i와 j부분 문자를 바꾼다.

그후 ans에 ans와 solve(sam, num + 1)중 더 큰 수를 집어넣는다.

모든 반복문이 완료되면 ans를 반환하며 ret에, 즉 cache에 ans값을 넣는다.

cin >> str >> k;
if (str.length() == 1 || (str.length() == 2 && str[1] == '0')) {
	cout << -1 << endl;
}
else {
	cout << solve(str, 0) << endl;
}

str과 k를 입력받은다음

만약 str의 길이가 1이거나 길이가 2인데 str의 두번째 문자가 0이라면 문자열을 만들수 없으니 -1을 출력한다.

아니라면 solve를 통해 정답을 출력한다.

#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;

string str;
string sam;
int cache[1000001][11];
int k;

int solve(string s, int num) {
	if (num == k) return stoi(s);
	int &ret = cache[stoi(s)][num];
	if (ret != -1) return ret;
	int ans = -1;

	for (int i = 0; i < s.length(); i++) {
		for (int j = i + 1; j < s.length(); j++) {
			if (i == 0 && s[j] == '0') continue;
			sam = s;
			swap(sam[i], sam[j]);
			ans = max(solve(sam, num + 1), ans);
		}
	}

	return ret = ans;
}

int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
	memset(cache, -1, sizeof(cache));

	cin >> str >> k;
	if (str.length() == 1 || (str.length() == 2 && str[1] == '0')) {
		cout << -1 << endl;
	}
	else {
		cout << solve(str, 0) << endl;
	}
}

전체코드다.