[Java] leetcode 1626. Best Team With No Conflicts

문제

https://leetcode.com/problems/best-team-with-no-conflicts/

Best Team With No Conflicts - LeetCode

Given two lists, scores and ages, where each scores[i] and ages[i] represents the score and age of the ith player, respectively, return the highest overall score of all possible basketball teams.

알아야 할 개념

• dfs 메모이제이션

풀이

풀이는 다음과 같다. 

1. ArrayList에 n번째 플레이어의 정보[score, age] 를 저장한다. 
2. age 순으로 오름차순 정렬 한다. 
3. 같은 age이면 score 순 오름차순 정렬
4. 재귀 함수를 만들어서 각 n번째 플레이어를 넣을지  말지 2가지 행동을 한다.
5. 메모이제이션으로 ( 현재 n번째 플레이어, max 플레이어 ) 값을 저장해 중복 탐색을 피한다.
6. 답을 리턴한다.

재귀함수의 해당 레벨에서 값을 구하면, (해당 인덱스와, max 인덱스) 위치의 값을 저장해야 중복 탐색을 피할 수 있다. 

prev 는 이전 max 인덱스 위치 를 나타내고 초기값을 -1 로 지정하기 때문에, 액세스할때 + 1 을 해준다.

 

코드

자바

class Solution {
    int memo[][];
    public int bestTeamScore(int[] s, int[] age) {
        List<int[]> l = new ArrayList<>();
        int n = s.length;
        memo = new int[n][n];
        for(int i = 0 ;i < n ;i++){
            l.add(new int[]{age[i],s[i]});
        }
        l.sort((a,b)->a[0]-b[0]==0 ? a[1]-b[1]: a[0]-b[0]);
        return dfs(l,0,-1);
    }
    public int dfs(List<int[]> l , int cur, int prev){
        if(cur > l.size()-1)return 0;
        if(memo[cur][prev+1]>0)return memo[cur][prev+1];
        
        if(prev==-1 || l.get(prev)[1] <= l.get(cur)[1] ){
           return memo[cur][prev+1] = Math.max(dfs(l,cur+1, cur)+l.get(cur)[1], dfs(l,cur+1,prev));
        }
        return memo[cur][prev+1] = dfs(l,cur+1,prev);
    }
    
}