[BOJ] 1519 부분 문자열 뽑기 게임

문제 링크

 

www.acmicpc.net/problem/1519

 

모든 알고리즘 문제는 C++로 구현되어 있습니다.

 

다이나믹 프로그래밍 사용해 풀 수 있는 문제이다. 이 문제의 핵심은 크게 두 가지로, 첫 번째는 어떤 수의 진 부분 문자열을 구하는 것이고, 두 번째는 승패를 판정하는 것이다.

 

부분 문자열을 뽑아내기 위해 나는 입력값을 string으로 받아 substr() 함수로 부분 문자열을 뽑아내고, stoi() 함수를 이용해 int형으로 바꿔서 뺄셈했다.

 

	for (i = 1; i < len; i++) { // i : 부분 문자열의 길이
		for (j = 0; j + i <= len; j++) { // 부분 문자열 시작 인덱스
			int sub = stoi(str.substr(j, i)); //int형으로 변환
			if (sub == 0) continue; // 0이면 continue
			// 재귀 처리
		}
	}

 

다음으로 승패를 판정하는 작업인데, 아래와 같은 함수를 사용했다.

 

int dp(string str) {
	if (str.length() == 1) {
		return -1;
	}
	int i, j, len=str.length(), num = stoi(str);
	int& ret = cache[num];
	if (ret != INF) return ret;
	bool vic = false;
	for (i = 1; i < len; i++) {
		for (j = 0; j + i <= len; j++) {
			int sub = stoi(str.substr(j, i));
			if (sub == 0) continue;
			if (dp(to_string(num - sub)) == -1) { // 이김
				vic = true;
				ret = min(ret, sub);
			}
		}
	}
	if (vic == false) ret = -1;
	return ret;
}

 

기본적으로 자신의 차례에 한 자리수 숫자를 만나게 되는 플레이어가 지게 된다. 이를 이용해 숫자가 한 자리수, 즉 str의 length가 1일 때 -1을 리턴하게 했다. 그 외의 경우 부분 문자열을 구해 뺀 값을 재귀 형식으로 다시 호출해주고, 이 값이 -1일 경우 상대 플레이어가 지는, 즉 현재 플레이어가 이기게 처리했다. 이 때 bool 형 변수 vic를 true로 바꿔주고, ret값을 ret값과 부분 문자열 값 중 더 작은 값으로 바꿔줬다(ret값 = cache 배열 값은 미리 1e9 + 7로 초기화해줬다). 만약 이길 수 있는 경우의 수가 없다면 ret 값을 -1로 바꿔줬다.

 

이렇게 하면 최종적으로 dp(처음 주어진 숫자)의 값은 부분 문자열 중 가장 작은 값이거나, 첫 플레이어가 이기는 방법이 없을 경우 -1이 될 것이다. 전체 코드는 아래와 같다.

 

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const int MAX = 1e6 + 1, INF=1e9+7;
int cache[MAX];

int dp(string str) {
	if (str.length() == 1) {
		return -1;
	}
	int i, j, len=str.length(), num = stoi(str);
	int& ret = cache[num];
	if (ret != INF) return ret;
	bool vic = false;
	for (i = 1; i < len; i++) {
		for (j = 0; j + i <= len; j++) {
			int sub = stoi(str.substr(j, i));
			if (sub == 0) continue;
			if (dp(to_string(num - sub)) == -1) { // 이김
				vic = true;
				ret = min(ret, sub);
			}
		}
	}
	if (vic == false) ret = -1;
	return ret;
}

int main() {
	string num;
	cin >> num;
	int i, j, len=num.length(), intNum=stoi(num);
	for (i = 0; i < MAX; i++) cache[i] = INF;
	cout << dp(num);
}

 

 

이렇게 하니 답은 구할 수 있었는데, 시간 컷에 아슬아슬하게 걸렸다(2초 제한에서 1.4초 정도). string으로 처리하지 말고 int 형으로 처리하는게 속도 면에서는 더 빠를 것 같다. 다음에 시간이 나면 좀 더 빠르게 풀 수 있도록 고쳐봐야겠다.