[백준] 2600번 : 구슬게임 (C++)

2600번 : 구슬게임

---

문제)

두 사람 A와 B가 번갈아 가면서 두 개의 구슬 통에서 몇 개씩의 구슬을 꺼내는 게임을 한다.

한번에 한 사람이 한 통에서 꺼낼 수 있는 구슬의 개수는 세 가지 뿐이다. 그리고 구슬을 꺼낼 경우 두 개의 구슬 통 중에서 하나를 마음대로 선택해서 그 안에서만 꺼낼 수 있다. 즉 두 개의 통 모두에서 동시에 몇 개씩 꺼낼 수는 없다.

게임은 항상 A가 먼저하고 그 다음 B, 그 다음 A 순으로 번갈아가면서 진행된다. 그리고 자신의 차례가 되었을 때에 정해진 규칙대로 구슬을 꺼낼 수 없는 사람이 게임에서 지게 되고, 상대방은 승리하게 된다.

예를 들어 한번에 꺼낼 수 있는 구슬의 개수를 1개, 3개, 또는 4개라고 하자. 만일 두 개의 구슬 통에 각각 4개, 1개의 구슬이 있다고 하면 처음 선택을 하게 되는 A가 이긴다. 그러나 만일 두 통속의 구슬이 각각 5개, 5개라면 B가 이긴다.

즉 한번에 꺼낼 수 있는 구슬 개수인 b1, b2, b3가 주어지고, 두 구슬 통 속에 들어있는 구슬의 수인 k1, k2이 정해지면, 이러한 b1, b2, b3와 k1, k2에 따라서 승패는 결정된다. 문제는 주어진 b1, b2, b3와 k1, k2에 대하여 A, B중 누가 승자인지를 결정하는 것이다.

처음 두 통 속에 들어 있는 구슬의 수 k1, k2와 한 번에 꺼낼 수 있는 구슬의 수 b1, b2, b3에 대한 제한조건은 다음과 같다.

• 1 ≤ b1 < b2 < b3 ≤ 30 
• 1 ≤ k1, k2 ≤500

 

 

 

입력 :

첫 줄에는 한번에 꺼낼 수 있는 구슬의 개수를 나타내는 세 개의 정수 b1, b2, b3 가 나타난다. 그 다음 5개의 각 줄에는 두 통속에 처음 담겨있는 구슬의 개수 k1, k2가 각각 표시되어 있다.

 

 

 

출력 :

각 5개의 k1, k2 경우에 대하여 그에 대응되는 승자(A 또는 B)를 각각 한 줄에 하나씩 차례대로 다섯 개를 출력해야 한다.

 

 

 

 

 

 

풀이)

 

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
vector<int> vec;
int a, b;
int dp[510][510];
 
int recur(int a, int b)
{
    // 기본적으로 A가 진다는 것으로 시작
    int ret = false;
 
    if (a == 0 && b == 0)
    {
        return 0;
    }
 
    if (dp[a][b] != -1)
    {
        return dp[a][b];
    }
 
 
    for (int i = 0; i < 3; i++)
    {
        if (a >= vec[i])
        {    // a - vec[i], b의 경우에는 A는 이길 수 있다.
            if (!recur(a - vec[i], b))
            {
                ret = true;
            }
        }
 
        if (b >= vec[i])
        {    // a ,b - vec[i]의 경우에는 A는 이길 수 있다.
            if (!recur(a, b - vec[i]))
            {
                ret = true;
            }
        }
    }
 
    dp[a][b]= ret;
 
    return dp[a][b];
}
 
int main()
{
    int temp;
    for (int i = 0; i < 3; i++)
    {
        cin >> temp;
        vec.push_back(temp);
    }
 
 
    for (int i = 0; i < 5; i++)
    {
        cin >> a >> b;
        fill(&dp[0][0], &dp[509][510], -1);
        cout << recur(a, b) << endl;
    }
 
    
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/2600 

2600번: 구슬게임