[백준, Java] 1519번, 부분 문자열 뽑기 게임, [DP, 그리디]

문제 링크

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

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. 자연수 N이 주어질 때 각 플레이어는 양수의 진 부분 문자열을 중 하나를 선택해서 기존 자연수에 빼는 행동을 진행합니다.

2. 플레이어가 부분 문자열을 선택할 수 없으면 게임에서 지게됩니다.

3. 플레이어1이 먼저 행동하며, 각 플레이어는 자신이 이길 수 있는 최선의 수를 선택합니다.

4. 플레이어1이 이기면 1, 지면 -1을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 메모이제이션, 재귀를 통한 게임에 과정을 탐색합니다.

 

3. 플레이어1이 이길 수 있는 방법이 있는지에 따른 결과를 출력합니다.

 

 

이길 수 있는 진 부분 문자열 선택하기(그리디)

 

부분 문자열을 선택할 때에는 2가지 경우가 존재합니다.

 

1. 이기는 경우의 수를 선택

 

부분 문자열 중에 1개라도 상대가 지는 경우가 존재할 때입니다.

 

왜냐하면, 항상 이기는 최상의 행동을 선택하기 때문에 상대가 지는 경우가 존재하면 해당 문자열을 선택하기 때문입니다.

 

 

2. 이기는 경우의 수가 없어서, 어떤 부분 문자열을 선택해도 질 때

 

모든 부분 문자열에 대해서 상대가 이기는 경우만 존재할 때입니다.

 

왜냐하면, 어떤 행동을 하더라도 상대가 이기는 경우밖에 존재하지 않기 때문에 항상 게임에서 질 수 밖에 없습니다.

 

중복된 문자열 탐색 예방하기(DP, 메모이제이션)

DP[i] : 현재 문자열의 i일 때 게임에서 이길 수 있는지 여부

 

1 : 게임 승리 경우 존재

 

-1 : 항상 게임 패배

 

0 : 탐색하지 않은 문자열

 

 

부분 문자열을 선택하는 과정이 달라지더라도 먼저 탐색했었던 i문자열에 도달한 경우, 기존에 탐색했던 정보 DP[i]을 이용하여 중복 탐색을 방지합니다.

 

부분 문자열

 

2309 : { 2, 3, 9, 12, 30, 230, 309}

 

부분 문자열을 구하는 방법은

 

2309 :

 

2309 % 10000 ( | 2309) ► ( | 2 |309), ( | 23 | 09) ...

 

2309 % 1000 (2 | 309) ► ( 2 | 3 | 09),  ( 2 | 30 | 9) ...

 

2309 % 100 ( 23 | 09) ► ...

 

2309 % 10 (230 | 9) ► ...

 

 

n % 10^(n+1) ÷ 10 ^ {n, n-1, ..., 1} 이 됩니다.

 

※ 참고로,  1 ~ 9는 부분 문자열을 만들 수 없기 때문에  i < 10이 만족하면 플레이어는 항상 지게 됩니다.

 

 

 

 

 

 

※예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 3.

 

1. 입력된 정보를 저장합니다.

 

N = 17

 

2. 메모이제이션, 재귀를 통한 게임에 과정을 탐색합니다.

 

DP[i] : 현재 문자열의 i일 때 게임에서 이길 수 있는지 여부

 

현재 문자열 : 17 (DP[17] = -1)

 

진 부분 문자열 : {1, 7}

 

{ 1 }일 때 : 16 (DP[16] = 1)

 

{ 7 }일 때 : 10 (DP[10] = 1)

 

 

현재 문자열 : 10 (DP[10] = 1)

 

진 부분 문자열 : {1}

 

{ 1 }일 때 : 9 → X 

 

 

현재 문자열 : 16(DP[16] = 1)

 

진 부분 문자열 : {1, 6}

 

{ 1 }일 때 : 15 (DP[15] = -1)

 

{ 6 }일 때 : 10 (DP[10] = 1)

 

...

 

현재 문자열 : 11 (DP[11] = -1)

 

진 부분 문자열 : {1}

 

{ 1 }일 때 : 10 (DP[10] = 1)

 

 

 

3. 플레이어1이 이길 수 있는 방법이 있는지에 따른 결과를 출력합니다.

 

탐색으로 DP[17] = -1이기 때문에 플레이어 1은 이길 수 있는 경우가 존재하지 않습니다.

 

-1 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• search함수를 통해서 플레이어를 이길 수 있는 경우를 탐색합니다.
• 탐색을 통해 조건에 만족하면 처음 선택하는 부분 문자열, 아니면 -1을 결과로 BufferdWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search함수는 부분 문자열에 재귀를 진행하여 이길 수 있는 여부를 탐색합니다.
• search함수는 DP[]을 이용해서 중복 탐색을 방지하고 있습니다.

결과코드

import java.io.*;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
    //문자열에 대해서 이길 수 있는지 메모이제이션 배열
    static int[] DP;
    static int N;
    static int min = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        DP = new int[N + 1];
        //플레이어 승리 여부 탐색 진행
        search(N);
        //이길 수 있는 경우가 존재하지 않을 때
        if(min == Integer.MAX_VALUE){
            min = -1;
        }
        //이길 수 있을 때 선택할 수 있는 부분 문자열 중 최소값 BufferedWriter 저장
        bw.write(String.valueOf(min));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //재귀, 메모이제이션을 통해 플레이어 승리 여부 탐색
    static int search(int cur){

        //이미 탐색한 내용이면 기존 탐색 내용 전달
        if(DP[cur] != 0){
            return DP[cur];
        }

        //10미만이면 부분 문자열이 존재하지 않아 패배한다.
        if(cur < 10){
            return DP[cur] = -1;
        }

        int remain = 1;
        //최초 나머지 값 구하기
        while(remain <= cur){
            remain *= 10;
        }

        //부분 문자열 탐색
        while(remain > 1){
            int temp = cur % remain;
            int div = 1;
            while(div <= temp){
                //부분 문자열
                int nxt = cur - (temp / div);
                if(nxt > 0){
                    //하위 문자열 중 하나라도 상대가 지는 경우가 존재할 때
                    if(search(nxt) == -1){
                        //지는 경우로 문자열을 변경하기 때문에 승리
                        DP[cur] = 1;
                        //처음일 때에 변경하는 부분 문자열 최소값 비교
                        if(cur == N){
                            min = Math.min(min, temp / div);
                        }
                    }
                }
                div *= 10;
            }
            remain /= 10;
        }

        //부분 문자열이 존재하지 않을 때
        if(DP[cur] == 0){
            return DP[cur] = -1;
        }

        //탐색한 정보 반환
        return DP[cur];
    }
}