문제 설명
두 개의 숫자 a와 b가 주어진다고 가정해 봅시다. 아말(Amal)과 비말(Bimal)은 각각 a개와 b개의 사탕을 들고 있습니다. 두 사람은 번갈아 가며 사탕을 주고받는데, 아말이 먼저 1개를 비말에게 건네면 비말은 2개를 아말에게 돌려줍니다. 다음 차례에는 아말이 3개, 비말이 4개를 주는 식으로 매번 한 개씩 더 많은 사탕을 주게 됩니다.
이 과정은 어느 한쪽이 요구된 만큼의 사탕을 더 이상 줄 수 없게 되는 순간까지 계속됩니다. 단, 상대방에게 받은 사탕은 자신의 것으로 치지 않는다는 점에 유의해야 합니다. 우리가 구해야 할 것은 처음으로 필요한 양만큼 사탕을 줄 수 없게 되는 사람입니다.
예시로 이해하기
입력이 a = 7, b = 6이라고 가정해 보겠습니다. 이때 출력은 Amal입니다. 처음에 아말이 1개를 주고, 비말이 2개를 줍니다. 이어서 아말이 3개, 비말이 4개를 줍니다. 그다음 아말의 차례에서는 5개를 줘야 하지만, 이미 사탕이 부족하여 더 이상 줄 수 없습니다. 따라서 먼저 실패하는 사람은 아말입니다.
풀이 접근 방법
매 차례를 일일이 시뮬레이션해도 되지만, 수학적 성질을 활용하면 상수 시간(O(1))에 답을 구할 수 있습니다.
아말은 홀수 개(1, 3, 5, …)를, 비말은 짝수 개(2, 4, 6, …)를 주므로 다음이 성립합니다.
- 아말이 자신의 k번째 차례까지 성공하려면 1 + 3 + … + (2k − 1) = k²개가 필요합니다. 즉, a ≥ k²이어야 합니다.
- 비말이 자신의 k번째 차례까지 성공하려면 2 + 4 + … + 2k = k(k + 1)개가 필요합니다. 즉, b ≥ k(k + 1)이어야 합니다.
a의 정수 제곱근을 x라고 하면, 아말은 최대 x번째 차례까지만 수행할 수 있습니다. (x + 1)²은 항상 a보다 크기 때문입니다. 이후 비말의 차례에서 b가 x × (x + 1)보다 작으면 비말이 먼저 실패하고, 그렇지 않으면 다음 아말의 차례에서 실패하게 됩니다.
이를 의사 코드로 나타내면 다음과 같습니다.
x := a의 제곱근
if x * (x + 1) > b, then:
return "Bimal"
Otherwise
return "Amal"
C++ 구현 예제
아래는 위 로직을 C++로 구현한 전체 코드입니다.
#include <bits/stdc++.h>
using namespace std;
string solve(int a, int b){
int x = sqrt(a);
if (x * (x + 1) > b)
return "Bimal";
else
return "Amal";
}
int main(){
int a = 7;
int b = 6;
cout << solve(a, b) << endl;
}
입력
7, 6
출력
Amal
마무리
이 문제는 단순 반복문 대신 제곱근과 등차수열의 합 공식을 활용하면 상수 시간에 해결할 수 있는 좋은 예입니다. 사탕을 주고받는 과정을 제곱수 관점에서 바라보면, 복잡해 보이는 시뮬레이션 문제도 단 한 줄의 조건문으로 바꿀 수 있습니다.