[백준 1519번] 부분 문자열 뽑기 게임 (C++)

문제링크 : https://www.acmicpc.net/problem/1519

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

string N;
int dp[1000001];

int func(string s)
{
    if(s.size()==1) return -1; //패배

    int n = stoi(s);
    if(dp[n]!=MAX) return dp[n];
    bool flag = 0; //승리, 패배 체크용

    for(int i=1; i<s.size(); i++) //길이
    {
        for(int j=0; j<=s.size()-i; j++)
        {
            int tmp = stoi(s.substr(j, i)); //j부터 i길이 만큼
            if(tmp==0) continue; //앞자리가 0이면 건너뜀
            if(func(to_string(n-tmp))!=-1) continue; //상대방이 -1이면 이김
            flag = 1; //승리 표시
            dp[n] = min(dp[n], tmp); //최소값 저장
        }
    }

    return (flag ? dp[n] : (dp[n] = -1));
}

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

    cin >> N;
    for(int i=0; i<1000001; i++) dp[i] = MAX;
    cout << func(N);
    return 0;
}

 

패배하게 되는 조건은 문자가 하나 밖에 남지 않아 더 이상 부분 문자열이 존재하지 못하게 되는 경우이다.

즉 현 문자열의 길이가 1인 경우로 볼 수 있다.

 

이중 반복문을 통해서 현재 가능한 문자열 길이를 기준으로 부분 문자열을 만들어 나간다.

substr 함수를 이용하여 기존 문자열 s에서 j를 기준으로 i길이 만큼 부분 문자열을 만들어 준다.

여기서 만든 부분 문자열의 맨 앞에 값이 0으로 시작하면 불가능한 경우이므로 스킵해준다.

 

이제 현재 값에서 새로 만든 부분 문자열을 빼서 만든 새로운 값(n-tmp)을 재귀로 넣어 다시 탐색하게 된다.

이렇게 넣은 값은 상대방의 차례에 해당하는 값이 된다.

해당 값을 기준으로 탐색을 이어 나갔을 때 최종적으로 -1을 반환하게 된다면 상대방이 진 것이 된다.

이를 이용하여 내 차례일 때 상대방 차례의 값을 재귀에 넣어 반환값이 -1이라면 내가 승리인 것을 알 수 있다.

만약 반환한 값이 -1이 아니라면 내가 진 것이므로 이후 과정은 스킵한다.

-1이라면 내가 이겼으므로 승리의 표시로 flag=1을 표시한 후 dp[n]에 최소값을 갱신하여 나가게 된다.

 

반복문이 모두 끝난 후에는 flag의 유무에 따라 승리시 dp[n]의 값을 패배시 dp[n]=-1을 저장하고 -1을 반환하게 된다.