1626. Best Team With No Conflicts

문제

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

내 코드

import java.util.*;

class Solution {

    class Node implements Comparable<Node>{
        int age;
        int score;

        public Node(int age, int score){
            this.age = age;
            this.score = score;
        }

        @Override
        public int compareTo(Node obj){
            if(this.score > obj.score)
                return 1;
            else if(this.score < obj.score)
                return -1;
            else if(this.age > obj.age)
                return 1;
            else if(this.age < obj.age)
                return -1;
            return 0;            
        }

        public String toString(){
            return "{age : " + this.age + ", " + "score : " + this.score + "}";
        }
    }


    public int bestTeamScore(int[] scores, int[] ages) {
        int N = ages.length;
        List<Node> list = new ArrayList<>();
        int[] dp = new int[N];
        for(int i=0; i<scores.length; i++)
            list.add(new Node(ages[i], scores[i]));
        Collections.sort(list);

        for(int i=0; i<N; i++){
            Node curNode = list.get(i);
            dp[i] = curNode.score;
            for(int j=i-1; j>=0; j--){
                Node tmpNode = list.get(j);
                if(tmpNode.age <= curNode.age)
                    dp[i] = Math.max(dp[i], curNode.score+dp[j]);                
            }
        }

        int max = 0;
        for(int i=0; i<N; i++)
            max = Math.max(dp[i], max);
        return max;
    }
}

피드백

conflict라는 게 문제였다. age가 높은 선수는 자신보다 age가 낮은 모든 선수보다 score가 높아야 한다는 제한조건이었다.
이 제한조건은 곧 score를 오름차순으로 정렬했을 때, age도 오름차순인 그룹만이 허용된다는 것을 뜻한다. 이러한 그룹은 여러 개가 존재했다. 문제는 곧 이러한 그룹 중 어떤 그룹의 value가 가장 높은지 찾는 dp 문제로 바뀔 수 있다.
그러면 dp식은 다음과 같다.

dp[i] = max(dp[i], dp[j] + score of i) (j <= i)

입력 길이 제한이 1000개임을 생각하면 O(N^2)이 가능했고 ack를 얻어낼 수 있었음.
이 문제는 백준에서 한 번 풀어본 문제임에도 불구하고 시간을 너무 많이 썻다 (1시간 20분)...