문제 개요
여러 문제가 출제되지만, 단 하나의 문제를 해결하는 순간 대회가 종료되는 프로그래밍 대회를 생각해 봅시다. 길이가 같은 두 개의 리스트 points와 chances가 주어지며, i번째 문제는 chances[i]%의 확률로 풀어서 points[i]점을 획득할 수 있습니다. 또한 시도할 수 있는 문제의 최대 개수를 나타내는 값 k가 주어지고, 동일한 문제는 두 번 시도할 수 없습니다.
최적의 전략을 세웠을 때 대회에서 얻을 수 있는 점수의 기댓값을 구하고, 그 값을 가장 가까운 정수로 반올림하는 것이 목표입니다. i번째 문제를 시도했을 때의 기댓값은 points[i] * chances[i] / 100.0으로 계산되며, 이는 해당 문제를 시도했을 때 평균적으로 얻게 되는 점수를 의미합니다.
예를 들어 points = [600, 400, 1000], chances = [10, 90, 5], k = 2가 입력으로 주어지면 출력은 392가 됩니다.
풀이 접근 방식
이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 문제에 대해 "시도한다" 또는 "건너뛴다"는 두 가지 선택지 중 더 큰 기댓값을 선택하는 것입니다.
- 먼저 모든 확률 값을 백분율에서 소수 형태로 변환합니다(
chances[i] /= 100.0). - 배점이 높은 문제부터 우선적으로 검토할 수 있도록 인덱스 배열을 points 내림차순 기준으로 정렬합니다.
dp(i, k)는 i번째 문제부터 고려하고 남은 시도 횟수가 k일 때 얻을 수 있는 최대 기댓값을 의미합니다.
dp 함수의 재귀 관계
- i가 n(문제 개수)과 같으면 더 이상 시도할 문제가 없으므로 0.0을 반환합니다.
- j := R[i] (배점 순으로 정렬된 i번째 문제의 원래 인덱스)
- p := chances[j] (해당 문제의 성공 확률)
- ev := p * points[j] (해당 문제를 시도할 때의 기댓값)
- 남은 시도가 1번뿐이라면(k == 1), 이 문제를 시도하는 것(ev)과 건너뛰는 것(dp(i + 1, k)) 중 큰 값을 반환합니다.
- 그렇지 않다면, 이 문제를 시도하는 경우(dp(i + 1, k - 1) * (1 - p) + ev)와 건너뛰는 경우(dp(i + 1, k)) 중 더 큰 값을 반환합니다. 즉, 실패 확률 (1 - p)로 가중치를 부여한 이후 상태의 기댓값에 이 문제의 기댓값 ev를 더한 값이 시도하는 경우의 총 기댓값입니다.
구현 예시
아래 파이썬 코드를 통해 더 자세히 이해해 보겠습니다.
class Solution:
def solve(self, points, chances, K):
n = len(points)
for i in range(n):
chances[i] /= 100.0
R = sorted(range(n), key=points.__getitem__, reverse=True)
def dp(i, k):
if i == n:
return 0.0
j = R[i]
p = chances[j]
ev = p * points[j]
if k == 1:
return max(ev, dp(i + 1, k))
return max(dp(i + 1, k - 1) * (1 - p) + ev, dp(i + 1, k))
return int(dp(0, K))
ob = Solution()
print(ob.solve([600, 400, 1000], [10, 90, 5], 2))입력
[600, 400, 1000], [10, 90, 5], 2
출력
392
정리
이 풀이는 각 문제에 대해 "시도"와 "건너뛰기" 두 선택지의 기댓값을 비교하는 재귀적 구조를 활용합니다. 배점이 높은 문제부터 차례로 검토함으로써, 제한된 시도 횟수 안에서 대회에서 달성할 수 있는 최대 기대 점수를 효율적으로 계산할 수 있습니다.