Search

PGS 주사위 고르기

태그
다이나믹 프로그래밍
누적 합
이분 탐색
매개 변수 탐색
생성일
2024/12/11 12:11

문제 설명

•
주어진 주사위 배열에서 AA가 승리 확률이 가장 높아지도록 (n//2)(n//2)개의 주사위를 선택하는 조합을 찾는 문제

예제 입력/출력

dice
result
[[1, 2, 3, 4, 5, 6], [3, 3, 3, 3, 4, 4], [1, 3, 3, 4, 4, 4], [1, 1, 4, 4, 5, 5]]
[1, 4]
[[1, 2, 3, 4, 5, 6], [2, 2, 4, 4, 6, 6]]
[2]
[[40, 41, 42, 43, 44, 45], [43, 43, 42, 42, 41, 41], [1, 1, 80, 80, 80, 80], [70, 70, 1, 1, 70, 70]]
[1, 3]

제약 조건

•
2≤n≤102 ≤ n ≤ 10
◦
nn은 2의 배수
◦
1≤1 ≤ dice[i]의 원소 ≤100≤ 100

문제 풀이

접근1 브루트 포스 - 상한 O(10C5⋅610)O(_{10}C_5 \cdot 6^{10})
접근2 파라매트릭 서치 - 상한 O( 10C5 ⋅ (65 + 65⋅log(65) ) )O( \ _{10}C_{5} \ \cdot \ (6^5 \ + \ 6^5 \cdot log (6^5) \ ) \ )
접근3 DP - 상한 O( 10C5 ⋅ (5⋅500⋅6) )O( \ _{10}C_5 \ \cdot \ (5 \cdot 500 \cdot 6) \ )

풀이 코드

접근1 브루트 포스 - 상한 O(10C5⋅610)O(_{10}C_5 \cdot 6^{10})
접근2 파라매트릭 서치 - 상한 O( 10C5 ⋅ (65 + 65⋅log(65) ) )O( \ _{10}C_{5} \ \cdot \ (6^5 \ + \ 6^5 \cdot log (6^5) \ ) \ )
접근3 DP - 상한 O( 10C5 ⋅ (500⋅500) )O( \ _{10}C_5 \ \cdot \ (500 \cdot 500) \ )
접근4 접근3 시간복잡도 개선 - 상한 O( 10C5 ⋅ (5⋅500⋅6) )O( \ _{10}C_5 \ \cdot \ (5 \cdot 500 \cdot 6) \ )

참고 자료