문제 링크
문제 요약
컬링 게임의 총 n개의 엔드(end)에 대한 최종 점수를 계산하는 문제입니다.
각 엔드마다 두 팀(A, B)의 필드 위에 남아있는 돌들의 좌표가 주어집니다. 컬링 경기장의 중심은 (0,0)으로 가정합니다.
득점 규칙은 다음과 같습니다:
- 각 엔드가 끝난 후, 두 팀 중 중심 (0,0)에 가장 가까운 돌을 가진 팀이 해당 엔드를 승리합니다.
- 승리한 팀은 자신의 돌들 중 상대 팀의 가장 가까운 돌보다 중심에 엄격히(strictly) 더 가까이 있는 돌 하나당 1점을 얻습니다.
- 만약 두 팀의 가장 가까운 돌들이 중심으로부터 같은 거리에 있다면, 해당 엔드에서는 어느 팀도 점수를 얻지 못합니다.
모든 엔드가 종료된 후, 최종 점수를
A:B형식으로 출력해야 합니다.
풀이
이 문제는 각 돌의 위치를 기준으로 중심 (0,0)으로부터의 거리를 계산하고, 이 거리를 기준으로 득점 규칙에 따라 점수를 계산하는 시뮬레이션 문제입니다.
핵심 아이디어는 다음과 같습니다:
-
거리 계산: 두 점 (x1, y1)과 (x2, y2) 사이의 거리는 입니다. 중심이 (0,0)이므로, 각 돌 (x, y)의 거리는 이 됩니다. 점들 간의 상대적인 거리만을 비교할 때는 제곱근을 계산할 필요 없이 값만으로도 충분합니다. 이는 부동 소수점 오차를 방지하고 연산 속도를 높이는 이점이 있습니다.
-
정렬: 각 팀의 돌들을 중심으로부터의 제곱 거리를 기준으로 오름차순으로 정렬합니다. 이렇게 하면 각 팀의
0번째 인덱스에 가장 가까운 돌의 정보가 위치하게 됩니다. -
득점 로직:
- 정렬된 팀 A의 첫 번째 돌의 제곱 거리 (
A[0][0])와 팀 B의 첫 번째 돌의 제곱 거리 (B[0][0])를 비교합니다. - Case 1:
A[0][0] < B[0][0](팀 A 승리)- 팀 A의 가장 가까운 돌이 팀 B의 가장 가까운 돌보다 엄격히 가깝습니다.
- 팀 A는 자신의 모든 돌을 순회하며, 각 돌의 제곱 거리(
A[i][0])가B[0][0]보다 엄격히 작은 경우(A[i][0] < B[0][0]) 1점을 얻습니다.
- Case 2:
A[0][0] > B[0][0](팀 B 승리)- 팀 B의 가장 가까운 돌이 팀 A의 가장 가까운 돌보다 엄격히 가깝습니다.
- 팀 B는 자신의 모든 돌을 순회하며, 각 돌의 제곱 거리(
B[i][0])가A[0][0]보다 엄격히 작은 경우(B[i][0] < A[0][0]) 1점을 얻습니다.
- Case 3:
A[0][0] == B[0][0](동점)- 두 팀의 가장 가까운 돌의 거리가 같습니다. 문제 규칙에 따라 이 엔드에서는 어느 팀도 점수를 얻지 못합니다.
- 정렬된 팀 A의 첫 번째 돌의 제곱 거리 (
이 과정을 n개의 모든 엔드에 대해 반복하여 최종 점수를 누적하고, 마지막에 A:B 형식으로 출력합니다.s
정답 코드
def f(l):
# (x, y) 좌표를 받아 (제곱 거리, x, y) 튜플을 반환합니다.
# 정렬 시 제곱 거리를 기준으로 정렬하기 위함입니다.
return [l[0] ** 2 + l[1] ** 2, l[0], l[1]]
def solve():
n = int(input()) # 엔드의 수
score = {'A': 0, 'B': 0} # 각 팀의 점수를 저장할 딕셔너리
for _ in range(n):
m, k = map(int, input().split()) # 팀 A의 돌 수 m, 팀 B의 돌 수 k
A = [f([*map(int, input().split())]) for _ in range(m)] # 팀 A의 돌 정보 (제곱 거리, x, y) 리스트
B = [f([*map(int, input().split())]) for _ in range(k)] # 팀 B의 돌 정보 (제곱 거리, x, y) 리스트
A.sort() # 팀 A의 돌들을 제곱 거리 기준으로 오름차순 정렬
B.sort() # 팀 B의 돌들을 제곱 거리 기준으로 오름차순 정렬
# 가장 가까운 돌의 거리를 비교하여 승자를 결정하고 점수를 계산
if A[0][0] < B[0][0]: # 팀 A의 가장 가까운 돌이 팀 B보다 가까울 때
cnt = 0
for i in range(m):
if A[i][0] < B[0][0]: # 팀 A의 돌이 팀 B의 가장 가까운 돌보다 엄격히 가까우면 점수 획득
cnt += 1
score['A'] += cnt
elif A[0][0] > B[0][0]: # 팀 B의 가장 가까운 돌이 팀 A보다 가까울 때
cnt = 0
for i in range(k):
if B[i][0] < A[0][0]: # 팀 B의 돌이 팀 A의 가장 가까운 돌보다 엄격히 가까우면 점수 획득
cnt += 1
score['B'] += cnt
else: # 두 팀의 가장 가까운 돌의 거리가 같을 때 (동점)
continue # 점수 변화 없음
print(f"{score['A']}:{score['B']}") # 최종 점수 출력
if __name__ == "__main__":
tc = 1
for t in range(1, tc+1):
ret = solve()