문제 이해하기
농구 경기에 참가하는 선수들을 대상으로 최고의 팀을 구성하는 문제를 살펴보겠습니다. 두 개의 리스트 scores와 ages가 주어지며, 여기서 scores[i]와 ages[i]는 i번째 선수의 점수와 나이를 나타냅니다.
우리의 목표는 팀 전체 점수(모든 선수 점수의 합)가 가장 높은 팀을 선택하는 것입니다. 다만 한 가지 중요한 제약 조건이 있습니다. 바로 게임 내에서 충돌(conflict)이 발생하면 안 된다는 점입니다. 충돌이란 더 어린 선수의 점수가 더 나이 많은 선수의 점수보다 엄격하게 높은 경우를 의미합니다.
예를 들어, scores = [5,7,9,14,19], ages = [5,6,7,8,9]가 입력으로 주어진다면, 모든 선수를 선택해도 충돌이 없으므로 출력값은 54가 됩니다.
해결 전략: 정렬과 동적 계획법(DP)
이 문제는 정렬과 동적 계획법을 결합하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 나이를 기준으로 선수들을 먼저 정렬한 후, 각 선수를 마지막으로 선택했을 때 얻을 수 있는 최대 점수를 누적 계산하는 것입니다. 다음 단계를 따릅니다.
- 1단계: 나이(a)와 점수(s)를 짝지어 sa라는 리스트를 생성합니다.
- 2단계: 리스트 sa를 오름차순으로 정렬합니다. 이렇게 하면 나이 순서대로 선수가 배치되어, 이후 선택 시 충돌 조건을 쉽게 검사할 수 있습니다.
- 3단계: 정렬된 sa에서 점수 값만 추출하여 새로운 scores 리스트를 만듭니다.
- 4단계: maxScore := 0으로 초기화합니다.
- 5단계: n := scores의 길이로 설정합니다.
- 6단계: 길이가 n인 배열 dp를 생성하고 0으로 채웁니다. dp[i]는 i번째 선수까지 고려했을 때의 최대 팀 점수를 저장합니다.
- 7단계: i를 0부터 n-1까지 반복하면서 다음을 수행합니다.
- score := scores[i]
- dp[i] := score
- j를 0부터 i-1까지 반복하며, 만약 scores[j] <= score라면 dp[i] := dp[i]와 dp[j] + score 중 최댓값으로 갱신합니다.
- 8단계: maxScore := maxScore와 dp[i] 중 최댓값으로 갱신합니다.
- 9단계: 모든 반복이 끝나면 maxScore를 반환합니다.
여기서 scores[j] <= score 조건이 중요합니다. 정렬된 상태에서 j번째 선수가 i번째 선수보다 나이가 같거나 어리므로, j번째 선수의 점수가 i번째 선수의 점수보다 크지 않다면 두 선수를 같은 팀에 합류시켜도 충돌이 발생하지 않기 때문입니다.
구현 예제 코드
이해를 돕기 위해 위 알고리즘을 파이썬으로 구현한 코드를 살펴보겠습니다.
def solve(scores, ages):
sa = [[a,s] for a,s in zip(ages,scores)]
sa.sort()
scores = [s for a,s in sa]
maxScore = 0
n = len(scores)
dp = [0] * n
for i in range(n):
score = scores[i]
dp[i] = score
for j in range(i):
if scores[j] <= score:
dp[i] = max(dp[i],dp[j] + score)
maxScore = max(maxScore, dp[i])
return maxScore
scores = [5,7,9,14,19]
ages = [5,6,7,8,9]
print(solve(scores, ages))
실행 결과 확인
입력
[5,7,9,14,19], [5,6,7,8,9]
출력
54
위 예제에서 나이순으로 정렬된 선수들의 점수 [5, 7, 9, 14, 19]는 이미 증가하는 형태이므로, 모든 선수를 한 팀에 포함시킬 수 있습니다. 따라서 전체 점수의 합인 54가 최종 결과로 반환됩니다.
시간 복잡도 분석
선수 정렬에는 O(n log n)의 시간이 소요되며, 이후 이중 반복문을 사용한 동적 계획법 과정에는 O(n²)의 시간이 걸립니다. 따라서 전체 시간 복잡도는 O(n²)이고, 추가 공간 복잡도는 dp 배열과 정렬된 리스트를 위해 O(n)입니다. 이 방식은 충돌 없는 최적 팀 구성 문제를 안정적이고 명확하게 해결할 수 있는 실용적인 접근법입니다.