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

문제 링크 => 1519번: 부분 문자열 뽑기 게임 (acmicpc.net)

1519번: 부분 문자열 뽑기 게임

---

다이나믹 프로그래밍 + 게임 이론 문제이다.

 

게임 이론이라는걸 이번에 처음 알게 되었다.

 

플레이어 1이 무조건 지게되는(필패) 경우를 찾고 dp 값을 업데이트 하는것을 기반으로 이 문제를 접근해 보려고 한다.

 

처음으로 N 값이 10 미만인 경우에 대해 살펴보면 이 경우는 필패이다.

=> 문제의 조건에서 "진 부분 문자열이란 자기 자신을 제외한 모든 연속된 부분 문자열을 말한다." 라고 명시되어 있으므로 10 미만의 숫자는 부분 문자열이 존재하지 않으므로 고를 수 없다. 

 

따라서 dp[ 1~9 ] = 0 으로 채워놓고 10 이상에 대해서 승, 패를 결정하는 과정을 살펴보도록 한다.

 

10인 경우 => 10의 부분 수열은 { 1 } 이다.

1을 선택하는 경우 ) 10 - 1 = 9 , 이때 9는 무조건 지게 되는 경우이므로 10은 무조건 이기게 된다.

따라서 dp[ 10 ] = 1 (이 때 1은 부분수열에 존재하는 값에서 이기게 되는 가장 작은 값)   

 

11인 경우 => 11의 부분 수열은 { 1 } 이다.

1을 선택하는 경우 ) 11 - 1 = 10 , 이때 10은 이기게 되는 경우이므로 11은 무조건 지게 된다.

따라서 dp[ 11 ] = 0

 

12인 경우 => 12의 부분 수열은 { 1, 2 } 이다.

1을 선택하는 경우 ) 12 - 1 = 11 , 이때 11은 무조건 지게 되므로  12은 무조건 이기게 된다.

2를 선택하는 경우 ) 12 - 2 = 10 , 이때 10은 무조건 이기게 되지만 1을 선택하는 경우 12는 무조건 이기게 되므로 pass

따라서 dp[ 12 ] = 1 (이 때 1은 부분수열에 존재하는 값에서 이기게 되는 가장 작은 값)   

 

...

 

N인 경우 => N의 부분 수열은 { a1, a2, ... , an } 이다.

ai ( 1 <= i <= n ) 를 선택하고 N - ai 값이 무조건 지게되는 경우를 찾게 되는 경우 N 값은 무조건 이기게 되며 이 경우를 만족하게 되는 aj 에 대하여 dp[ N ] = min(aj) 를 해주면 된다.  

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#define INF 100000000
#define endl '\n'
#define ll long long

using namespace std;

int dp[1000001];

vector<int> getSet(string s) {
	vector<int> ret;

	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '0') continue;
		string tmp = "";
		for (int j = i; j < s.size(); j++) {
			tmp = tmp + s[j];
			if (s != tmp) {
				ret.push_back(stoi(&tmp[0]));
			}
		}
	}

	return ret;
}

void solve() {
	
	string s;
	cin >> s;
	int n = stoi(&s[0]);

	if (n < 10) cout << -1;
	else {		
		for (int i = 10; i <= n; i++) {
			vector<int> v = getSet(to_string(i));
			int x = 1000001;
			for (int j = 0; j < v.size(); j++) {
				if (dp[i - v[j]] == 0) {
					x = min(x, v[j]);
				}
			}
			if (x != 1000001) {
				dp[i] = x;
			}
		}
		cout << (dp[n] == 0 ? -1 : dp[n]) << endl;
	}
}

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

	solve();

	return 0;
}