문제 설명
네 개의 정수 n1, n2, k1, k2가 주어진다고 가정해 봅시다. 두 개의 상자가 있는데, 첫 번째 상자에는 n1개의 공이, 두 번째 상자에는 n2개의 공이 들어 있습니다. Amal과 Bimal이라는 두 사람이 이 게임을 진행합니다.
게임 규칙은 다음과 같습니다.
- Amal은 자신의 차례에 첫 번째 상자에서 1개부터 k1개까지의 공을 꺼내 던져 버립니다.
- Bimal은 자신의 차례에 두 번째 상자에서 1개부터 k2개까지의 공을 꺼내 던져 버립니다.
- Amal이 먼저 시작하며, 두 사람은 번갈아 가며 플레이합니다.
- 자신의 차례에 공을 꺼낼 수 없는 사람이 패배합니다.
우리의 목표는 두 사람 중 누가 최종 승자인지 알아내는 것입니다.
예시
입력이 n1 = 2, n2 = 2, k1 = 1, k2 = 2라고 가정해 보겠습니다. 이 경우 출력은 Bimal입니다. 두 상자 모두 공이 2개씩 들어 있고, Amal이 첫 번째 상자에서 공 1개를 꺼내면 Bimal은 두 번째 상자에서 1개 또는 2개의 공을 꺼낼 수 있습니다. Amal이 어떻게 행동하든 Bimal은 최적의 전략으로 플레이하면 항상 승리할 수 있습니다.
해결 접근 방식
이 문제의 핵심은 k1과 k2 값은 사실 결과에 영향을 주지 않는다는 점입니다. 각 플레이어는 자신의 상자에서만 공을 꺼낼 수 있으므로, 상자가 먼저 빈 쪽이 패배하게 됩니다. 즉, 더 많은 공을 가진 플레이어가 항상 이길 수 있습니다.
구체적인 로직은 다음과 같습니다.
n1 > n2이면:
"Amal" 반환
그렇지 않으면:
"Bimal" 반환
n1이 n2보다 크다면 Amal은 매번 1개씩만 꺼내는 방식으로 오래 버틸 수 있지만, Bimal은 최대 n2턴 안에 자신의 상자를 비우게 됩니다. 반대로 n1이 n2보다 작거나 같으면 Bimal이 매번 1개씩만 꺼내는 전략으로 Amal보다 오래 생존할 수 있으므로 Bimal이 승리합니다.
C++ 구현 예제
이해를 돕기 위해 다음 구현 예제를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
string solve(int n1, int n2, int k1, int k2) {
if (n1 > n2)
return "Amal";
else
return "Bimal";
}
int main() {
int n1 = 2;
int n2 = 2;
int k1 = 1;
int k2 = 2;
cout << solve(n1, n2, k1, k2) << endl;
}
입력
2, 2, 1, 2
출력
Bimal