[백준, Java] 2600번, 구슬게임, (DP)

문제 링크

2600번: 구슬게임

---

주의사항

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

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

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. b1, b2, b3 개수만큼 주머니에서 구슬을 꺼낼 수 있습니다.

2. 구슬을 꺼낼 때에는 1개의 주머니에서만 꺼낼 수 있습니다.

3. A부터 꺼내기 시작해서, 순서대로 반복합니다.

4. 구슬을 꺼낼 수 없는 경우 상대방이 승리합니다.

5. 주머니의 구슬 개수가 주어질 때 누가 이기는지 결과로 출력합니다.

 

알고리즘 진행 순서.

 

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

 

2. 구슬을 꺼내는 과정을 탐색합니다.

 

3. 탐색을 통해 승리한 사람을 결과로 출력합니다.

 

구슬 꺼내기(DP)

 

구슬을 꺼낼 때에는 항상 자신이 이길 수 있는 경우의 수를 선택해야 합니다.

 

꺼낼 수 있는 경우가 3가지가 있을 경우, 그 중 1가지라도 자신이 이길 수 있는 경우의 수이면 해당 경우의 수 형태로 구슬을 꺼내야 합니다.

 

 

예를 들어, 2개의 바구니에서는 4개, 0개가 존재할 때, (b1, b2, b3) → (1, 3, 4)

 

 

 

 

추후에 나올 수 있는 경우

 

1. ( 3, 0 )

 

2. ( 1, 0 ) 

 

3. ( 0, 0 )

 

이 중 1개라도 내가 상대방이 지는 경우의 수가 존재한다면, 해당 경우의 수로 구슬을 꺼낸다는 이야기입니다.

 

그러면 구슬을 꺼내는 과정에서 발생할 수 있는 경우의 수는 2가지입니다.

 

 

1. 구슬을 뺀 상황에서 상대방이 지는 경우가 존재한다.

 

해당 경우로 구슬을 빼는 과정을 진행합니다.

 

2. 구슬을 뺀 상황 모두 상대방이 이기는 경우일 때

 

구슬을 어떻게 꺼내와도 모두 상대방이 이기기 때문에 현재 주머니 상황에서는 이길 수 없습니다.

 

 

위 2경우의 수를 고려해서 나올 수 있는 모든 주머니의 경우의 수를 구한 뒤 상황에 맞는 승자를 결과로 출력하였습니다.

 

 

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

 

예제입력 1.

 

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

 

{ b1, b2, b3 } : 1, 3, 4

 

 

※ 1번째 테스트 케이스만 진행하도록 하겠습니다.

 

2. 구슬을 꺼내는 과정을 탐색합니다.

 

DP[i][j] : 2개의 주머니의 구슬의 개수가 i개, j개 있을 때

 

※ DP[0]이 1인 이유는 빈 암호 코드에 암호가 추가면 그 자체가 경우의 수가 되기 때문입니다.

 

 

구슬의 최대 개수는 DP[500][500]까지 가능하지만 이번 경우에는최대 4개이기 때문에 DP[4][4]까지만 구해보도록 하겠습니다.

 

	0	1	2	3	4
0	X	O	X	O	O
1	O	X	O	X	O
2	X	O	X	O	O
3	O	X	O	X	O
4	O	O	O	O	X

 

 

(0, 0)은 항상 구슬을 꺼낼 수 없기 때문에 지게 됩니다.

 

DP[0][1] → (0, 0) : (0, 0)으로 만들면 상대방은 지는 경우 존재해서 해당 경우에는 이길 수 있습니다.

 

DP[0][2] → (0, 1) : 만드는 모든 경우가 상대방이 이기는 경우라서 해당 경우에는 질 수 밖에 없습니다.

 

DP[0][3] → (0, 2), (0, 0) : (0, 0)으로 만들면 상대방은 지는 경우 존재해서 해당 경우에는 이길 수 있습니다.

 

DP[0][4] → (0, 3), (0 , 1), (0, 0) : (0, 0)으로 만들면 상대방은 지는 경우 존재해서 해당 경우에는 이길 수 있습니다.

 

-----------------------------------------------------

 

 

DP[1][0] → (0, 0) : (0, 0)으로 만들면 상대방은 지는 경우 존재해서 해당 경우에는 이길 수 있습니다.

 

DP[1][1] → (1, 0), (0, 1) : 만드는 모든 경우가 상대방이 이기는 경우라서 해당 경우에는 질 수 밖에 없습니다.

 

DP[1][2] → (0, 2), (1, 1) : (1, 1) 으로 만들면 상대방은 지는 경우 존재해서 해당 경우에는 이길 수 있습니다.

 

DP[1][3] → (0, 3), (1, 2), (1, 0) : 만드는 모든 경우가 상대방이 이기는 경우라서 해당 경우에는 질 수 밖에 없습니다.

 

DP[1][4] → (0, 4), (1 , 3), (1, 1), (1, 0) : (1, 3)으로 만들면 상대방은 지는 경우 존재해서 해당 경우에는 이길 수 있습니다.

 

-----------------------------------------------------

 

DP[2][0] → (1, 0) : 만드는 모든 경우가 상대방이 이기는 경우라서 해당 경우에는 질 수 밖에 없습니다.

 

DP[2][1] → (1, 1), (2, 0) : (2, 0)으로 만들면 상대방은 지는 경우 존재해서 해당 경우에는 이길 수 있습니다.

 

DP[2][2] → (1, 2), (2, 1) : 만드는 모든 경우가 상대방이 이기는 경우라서 해당 경우에는 질 수 밖에 없습니다.

 

DP[2][3] → (1, 3), (2, 2), (2, 0) : (2, 0) 으로 만들면 상대방은 지는 경우 존재해서 해당 경우에는 이길 수 있습니다.

 

DP[2][4] → (1, 4), (2, 3), (2, 1), (2, 0) : (2, 0)으로 만들면 상대방은 지는 경우 존재해서 해당 경우에는 이길 수 있습니다.

 

-----------------------------------------------------

 

DP[3][0] → (2, 0), (0, 0) :  (0, 0)으로 만들면 상대방은 지는 경우 존재해서 해당 경우에는 이길 수 있습니다.

 

DP[3][1] → (2, 1), (0, 1), (3, 0) : 만드는 모든 경우가 상대방이 이기는 경우라서 해당 경우에는 질 수 밖에 없습니다.

 

DP[3][2] → (2, 2), (0, 2), (3, 1) : (0, 2) 으로 만들면 상대방은 지는 경우 존재해서 해당 경우에는 이길 수 있습니다.

 

DP[3][3] → (2, 3), (0, 3), (3, 2) : 만드는 모든 경우가 상대방이 이기는 경우라서 해당 경우에는 질 수 밖에 없습니다.

 

DP[3][4] → (2, 4), (0, 4), (3, 3), (3, 1), (3, 0) : (3, 3)으로 만들면 상대방은 지는 경우 존재해서 해당 경우에는 이길 수 있습니다.

 

-----------------------------------------------------

 

DP[4][0] → (3, 0), (1, 0), (0, 0) :  (0, 0)으로 만들면 상대방은 지는 경우 존재해서 해당 경우에는 이길 수 있습니다.

 

DP[4][1] → (3, 1), (1, 1), (0, 1), (4, 0) :  (1, 1)으로 만들면 상대방은 지는 경우 존재해서 해당 경우에는 이길 수 있습니다.

 

DP[4][2] → (3, 2), (1, 2), (0, 2), (4, 1) : (0, 2) 으로 만들면 상대방은 지는 경우 존재해서 해당 경우에는 이길 수 있습니다.

 

DP[4][3] → (3, 3), (1, 3), (0, 3), (4, 2), (4, 0) : (3, 3)으로 만들면 상대방은 지는 경우 존재해서 해당 경우에는 이길 수 있습니다.

 

DP[4][4] → (3, 4), (1, 4), (0, 4), (4, 3), (4, 1), (4, 0) : 만드는 모든 경우가 상대방이 이기는 경우라서 해당 경우에는 질 수 밖에 없습니다.

 

3. 탐색을 통해 승리한 사람을 결과로 출력합니다.

 

두 바구니 구슬의 개수가 (4, 1)이기 때문에 결과는 DP[4][1]이 됩니다.

 

DP[4][1]은 승리하기 때문에 A가 승리합니다.

 

A 결과로 출력합니다.

 

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 통해서 구슬 정보를 띄어쓰기 기준 나누었습니다.
• 주머니에 구슬을 꺼내는 개수와 주머니의 상황에 따른 승자/패자를 탐색하여 DP[][]에 저장합니다.
• 입력받은 상황에 따른 승자/패자를 BufferdWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

결과코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    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));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int[] b = new int[3];
        //구슬 최대 개수
        int maxSize = 500;
        //꺼내는 구슬 개수 저장
        for(int i=0;i<3;i++){
            b[i] = Integer.parseInt(st.nextToken());
        }
        //오름차순 정렬
        Arrays.sort(b);
        int[][] DP = new int[maxSize+1][maxSize+1];
        /**
         * 1 : 패배
         * 2 : 승리
         */
        //[0][0]은 구슬을 꺼내지 못하기 때문에 항상 패배
        DP[0][0] = 1;
        //DP[][]정보 경우에 따라 적용
        for(int i=0;i <= maxSize;i++) {
            for (int j = 0; j <= maxSize; j++) {
                //더 이상 구슬을 꺼낼 수 없는 경우
                if (i < b[0] && j < b[0]) {
                    DP[i][j] = 1;
                    continue;
                }
                //[i]부분 주머니 구슬 꺼내기
                for (int k = 0; k < 3; k++) {
                    if (i - b[k] < 0) {
                        break;
                    }
                    if (DP[i - b[k]][j] == 1) {
                        DP[i][j] = 2;
                        break;
                    }
                }
                //[j]부분 주머니 구슬 꺼내기
                if (DP[i][j] == 0) {
                    for (int k = 0; k < 3; k++) {
                        if (j - b[k] < 0) {
                            break;
                        }
                        if (DP[i][j - b[k]] == 1) {
                            DP[i][j] = 2;
                            break;
                        }
                    }
                }
                //모든 상황이 상대방이 승리하는 경우
                if(DP[i][j] == 0){
                    DP[i][j] = 1;
                }
            }
        }
        //각 상황에 맞는 승자 BufferedWriter 저장
        for(int i=0;i<5;i++){
            st = new StringTokenizer(br.readLine()," ");
            int k1 = Integer.parseInt(st.nextToken());
            int k2 = Integer.parseInt(st.nextToken());
            if(DP[k1][k2] == 2){
                bw.write("A");
            }else{
                bw.write("B");
            }
            bw.newLine();
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }

}