두 개의 정수 n과 k가 주어졌다고 가정해 봅시다. 아말(Amal)과 비말(Bimal)은 간단한 규칙의 게임을 진행합니다. 먼저 아말이 일렬로 n개의 막대기를 그린 뒤, 두 플레이어는 번갈아 가며 자신의 차례마다 왼쪽 또는 오른쪽 끝에서 정확히 k개의 막대기를 지웁니다. 아말이 선공입니다. 만약 어떤 차례가 시작되기 전에 남아 있는 막대기가 k개 미만이라면 게임은 종료됩니다. 아말이 비말보다 엄격하게 많은 횟수로 움직였을 때만 아말이 승리하며, 우리는 최종 승자가 누구인지 판별해야 합니다.
예를 들어 입력이 n = 10, k = 4라고 해보겠습니다. 이 경우 출력은 Bimal입니다. 아말이 먼저 4개의 막대기를 지우고, 비말도 이어서 4개를 지우면 남은 막대기는 2개뿐입니다. 따라서 아말은 더 이상 움직일 수 없으며, 두 플레이어의 움직임 횟수가 동일하기 때문에 아말은 승리하지 못합니다.
문제 해결 접근 방법
이 문제는 게임 전체에서 가능한 최대 움직임 횟수를 생각하면 매우 간단하게 해결할 수 있습니다.
- 게임 전체에서 발생하는 총 움직임 횟수는 floor(n / k)입니다.
- 아말이 선공이므로, 총 움직임 횟수가 홀수라면 아말이 한 번 더 움직이게 되어 승리합니다.
- 반대로 총 움직임 횟수가 짝수라면 두 플레이어의 움직임 횟수가 같아지므로 아말은 승리 조건을 충족하지 못합니다.
따라서 다음과 같은 절차로 답을 구할 수 있습니다.
floor(n / k)가 홀수이면: return "Amal" return "Bimal"
예제 코드
아래의 C++ 구현을 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
string solve(int n, int k) {
if ((n / k) % 2 != 0) {
return "Amal";
}
return "Bimal";
}
int main() {
int n = 10;
int k = 4;
cout << solve(n, k) << endl;
}
입력
10, 4
출력
Bimal
정리
이 문제의 핵심은 나눗셈의 몫인 floor(n / k)가 홀수인지 짝수인지만 확인하면 된다는 점입니다. 시간 복잡도는 O(1)로, n과 k의 크기와 무관하게 즉시 승자를 판별할 수 있어 매우 효율적인 해결 방식입니다.