1626. Best Team With No Conflicts
https://leetcode.com/problems/best-team-with-no-conflicts/
문제
풀이(DP)
scores = [6, 8, 1, 15, 3, 4, 9, 15, 20, 7]
ages = [1, 1, 2, 2, 2, 3, 3, 3, 4, 4]라고 할 때
먼저 나이별 점수리스트 목록을 추출한다. 즉
dp[(1)] = [8, 6] => 나이가 1인 점수 리스트
dp[(2)] = [15, 3, 1] => 나이가 2인 점수 리스트
dp[(3)] = [15, 9, 4] => 나이가 3인 점수 리스트
dp[(4)] = [20, 7] => 나이가 4인 점수 리스트 로 나눌 수 있다. (내림차순 적용)
이제 DP를 적용하면 된다.
나이를 내림차순으로 정렬하여 나이가 많은 사람먼저 계산하도록 한다. (이전 최대값을 이용하기 위해서)
ages = [4, 3, 2, 1]이 될 것이고 점화식은 다음과 같다.
max_value = max(st[1] + score, prev + score) => (st는 스택, prev는 이전 최대값)
ages = 4이고 score = 6일 때를 보자
tmp 칸에 max(56, 50, 33, 64) = 64 적혀져있다.
그 이유는 ages = 3일 때 6보다 크거나 같은 점수는 15이고 15에 값은 50이기에 50+6 = 56이 된다.
ages = 2일 때 6보다 크거나 같은 점수는 9이고 9에 값은 44이기에 50이 된다.
ages = 1일 때 6보다 크거나 같은 점수는 7이고 7에 값은 27이기에 33이 된다.
prev(이전값) = 58이므로 58+6 = 64가 된다. 이 중 max값을 저장하면 된다.
이렇게 하여 tmp에 저장된 값중 최대값을 리턴하면 된다.
결과(DP)
