Amal과 Bimal이 돌 가져오기 게임을 하고 있으며, Amal이 먼저 시작한다고 가정해 보겠습니다. 게임의 규칙은 다음과 같습니다.
한 더미에 n개의 돌이 놓여 있습니다. 각 플레이어는 자신의 차례에 돌 하나를 가져가며, 해당 돌의 위치에 따라 점수를 받게 됩니다. 흥미로운 점은 Amal과 Bimal이 같은 돌을 서로 다르게 평가할 수 있다는 것입니다.
두 개의 배열 A_Values와 B_Values가 주어집니다. A_Values[i]는 Amal이, B_Values[i]는 Bimal이 i번째 돌에 부여하는 가치를 나타냅니다. 모든 돌을 가져간 뒤 점수가 더 높은 사람이 승리하고, 점수가 같으면 무승부가 됩니다.
두 플레이어 모두 최선의 전략으로 플레이하며, 상대방이 각 돌을 어떻게 평가하는지도 알고 있습니다. 결과는 다음과 같이 반환합니다.
- Amal이 승리하면 → 1
- Bimal이 승리하면 → -1
- 무승부라면 → 0
예시
예를 들어 A_Values = [2, 4], B_Values = [3, 5]라고 입력이 주어졌을 때 출력은 1입니다. 그 이유는 Amal이 가치가 4인 두 번째 돌을 먼저 가져가면, Bimal은 남은 첫 번째 돌(가치 3)을 가져갈 수밖에 없습니다. 결국 Amal의 점수가 더 높아 Amal이 승리하게 됩니다.
문제 해결 접근 방법
이 문제는 탐욕적(Greedy) 전략으로 해결할 수 있습니다. 핵심 아이디어는 각 돌의 '경쟁 가치', 즉 두 플레이어의 평가 가치를 합산한 값이 가장 큰 돌부터 차례대로 가져가는 것입니다. 어떤 돌이든 두 플레이어의 가치 합이 크다는 것은 그만큼 양쪽 모두에게 중요한 돌이라는 의미이므로, 이를 기준으로 정렬하여 번갈아 선택하면 최적의 결과를 얻을 수 있습니다.
구체적인 단계는 다음과 같습니다.
- n := A_Values의 길이로 설정합니다.
- combinedValues라는 새 리스트를 만듭니다.
- i를 0부터 n-1까지 반복하면서 다음을 수행합니다.
- tmpV := A_Values[i] + B_Values[i]
- (tmpV, i) 쌍을 combinedValues 끝에 추가합니다.
- combinedValues를 내림차순으로 정렬합니다.
- score_a := 0, score_b := 0으로 초기화합니다.
- i를 0부터 n-1까지 반복하면서 다음을 수행합니다.
- curV := combinedValues[i]
- i가 짝수이면(Amal 차례) score_a에 A_Values[curV[1]]을 더합니다.
- i가 홀수이면(Bimal 차례) score_b에 B_Values[curV[1]]을 더합니다.
- score_a > score_b이면 1을 반환합니다.
- score_a == score_b이면 0을 반환합니다.
- 그 외의 경우에는 -1을 반환합니다.
구현 예제
아래 코드를 통해 더 잘 이해해 보겠습니다.
def solve(A_Values, B_Values):
n = len(A_Values)
combinedValues = []
for i in range(n):
tmpV = A_Values[i] + B_Values[i]
combinedValues.append([tmpV, i])
combinedValues.sort(reverse=True)
score_a, score_b = 0, 0
for i in range(n):
curV = combinedValues[i]
if (i % 2 == 0):
score_a += A_Values[curV[1]]
else:
score_b += B_Values[curV[1]]
if (score_a > score_b):
return 1
elif (score_a == score_b):
return 0
else:
return -1
A_Values = [2,4]
B_Values = [3,5]
print(solve(A_Values, B_Values))입력
[2,4], [3,5]
출력
1
정리
이 풀이의 시간 복잡도는 정렬 과정이 지배하므로 O(n log n)입니다. 각 돌의 가치 합을 기준으로 내림차순 정렬한 뒤, 앞에서부터 번갈아 배분하는 방식이 두 플레이어 모두 최적으로 행동할 때의 게임 결과와 일치한다는 점이 이 문제의 핵심입니다.