n개의 카드와 크기가 각각 k1, k2인 두 배열 A와 B가 주어진다고 가정해 봅시다. Amal과 Bimal이 흥미로운 카드 게임을 하고 있는 상황입니다. 카드는 총 n장으로 1부터 n까지 번호가 매겨져 있으며, 처음에 두 사람에게 나누어집니다.
게임의 진행 방식은 다음과 같습니다. 매 턴마다 각 플레이어는 자신이 가진 카드 중 원하는 카드 하나를 골라, 상대방이 어떤 카드를 냈는지 보지 못한 상태로 테이블에 놓습니다. 이후 두 카드가 동시에 공개되고, 더 큰 숫자가 적힌 카드를 낸 플레이어가 두 카드를 모두 가져갑니다. 여기서 중요한 규칙은 같은 카드를 몇 번이고 반복해서 사용할 수 있다는 점입니다. 배열 A는 Amal이 가진 카드, 배열 B는 Bimal이 가진 카드를 의미하며, 손에 카드가 하나도 남지 않는 플레이어가 패배합니다. 우리는 최종 승자를 구해야 합니다.
예를 들어 입력이 n = 5; A = [3, 2]; B = [5, 1, 4]라고 해봅시다. 이 경우 출력은 'Bimal'입니다. 처음에 (3, 5)를 내면 Bimal이 모든 카드를 가져가고, 이어서 (3, 1)을 내면 Amal이 두 장을 되찾습니다. 다시 (3, 4)를 내면 Bimal이 전부 가져가며, 마지막으로 Amal이 1을 내면 Bimal은 5로 받아내기 때문에 결국 Amal의 손에는 카드가 남지 않습니다.
핵심 아이디어
같은 카드를 무제한으로 다시 사용할 수 있다는 규칙 때문에 이 문제는 생각보다 훨씬 간단하게 풀립니다. 어느 한쪽이 가장 큰 숫자의 카드를 가지고 있다면, 그 카드를 계속 내면서 상대의 카드를 하나씩 모두 가져올 수 있기 때문입니다. 따라서 A의 최댓값과 B의 최댓값을 서로 비교하기만 하면 되고, 더 큰 값을 가진 플레이어가 최종 승자가 됩니다.
풀이 단계
문제를 해결하기 위해 다음 단계를 따릅니다.
d := 0
e := 0
i := 0부터 A의 크기보다 작을 때까지 반복(i는 1씩 증가):
f := A[i]
만약 d < f이면:
d := f
i := 0부터 B의 크기보다 작을 때까지 반복(i는 1씩 증가):
f := B[i]
만약 e < f이면:
e := f
만약 d > e이면:
'Amal' 반환
그렇지 않으면:
'Bimal' 반환
C++ 구현 예제
더 나은 이해를 돕기 위해 실제 구현 코드를 살펴보겠습니다. 시간 복잡도는 두 배열을 한 번씩 순회하므로 O(k1 + k2)로 매우 효율적입니다.
#include<bits/stdc++.h>
using namespace std;
string solve(int n, vector<int> A, vector<int> B){
int d = 0;
int e = 0;
// A의 최댓값 구하기
for(int i = 0; i < A.size(); i++){
int f = A[i];
if (d < f)
d = f;
}
// B의 최댓값 구하기
for(int i = 0; i < B.size(); i++){
int f = B[i];
if (e < f)
e = f;
}
if (d > e)
return "Amal";
else
return "Bimal";
}
int main(){
int n = 5;
vector<int> A = {3, 2};
vector<int> B = {5, 1, 4};
cout << solve(n, A, B) << endl;
}
입력
5, {3, 2}, {5, 1, 4}출력
Bimal