[백준 11055] 가장 큰 증가하는 부분 수열 (JAVA)

백준 11055번 문제 - 가장 큰 증가하는 부분 수열

11055번: 가장 큰 증가하는 부분 수열

---

문제 분석

 

• 가장 큰 증가하는 부분 수열
  • 가장 큰 증가하는 부분 수열 : 만들어진 부분수열 중 오름차순으로 정렬된 합이 가장 큰 수
• 주어진 수열에서 가장 큰 증가하는 부분 수열의 길이를 출력

---

 

해결 키 포인트

 

• 어떻게 설계 할 수 있을까 ?
  • 맨 뒤부터 가능한 최장 수열 길이 구하기 방식으로 각 인덱스들의 sum 구한 후, 가장 큰 sum 출력
    WHY? 앞에 있는 수들은 뒤에 구해진 최장 수열의 합으로 구하면 계산이 더 간단해지므로~!
• 어떻게 구현하지 ?
  • 내가 필요한 수는 해당 숫자부터 시작했을 때 최장 수열 합과 해당 숫자
    → Node class 만들어서 두개 다 관리하기 편하게
    + 근데 지금 생각하면 숫자 array와 sum array의 index만 동일하게 해도 됐을 듯 !
  • 해당 index 이후 node들의 sum 값들을 통해 현재 값의 최장 수열 합 알아내기
  • nodes 배열에 추가 (구한 sum + nums[i] )
  • nodes 배열을 len 합 순으로 내림차순 나열 ( 가장 큰 len 출력 : index 0번 째 )

implements Comparable<Node> {                          
      @Override                                                            
      public int compareTo(Node n) { return ~; }       
}                                                                                   

 

---

코드

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 수열의 크기(N) 입력
        int N = Integer.parseInt(br.readLine());

        // 수열 입력
        int[] nums = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        // nodes 배열은 nums[i]와 i부터 수열을 시작했을 때 최장 수열 len을 기록
        ArrayList<Node> nodes = new ArrayList<>();

        // 뒤에서부터 최장 수열 합 확인
        for (int i = N - 1; i >= 0; i--) {
            int sum = 0;

            // nodes에 있는 sum 값들을 통해 현재 값의 최장 수열 합 알아내기
            for (int j = nodes.size() - 1; j >= 0; j--) {
                Node node = nodes.get(j);

                // 만약 현재 수가 해당 node의 수보다 크고 sum도 해당 수보다 클 경우 -> sum 변경
                if (node.num > nums[i] && sum < node.sum)
                    sum = node.sum;
            }
            // nodes 배열에 추가
            nodes.add(new Node(nums[i], sum + nums[i]));
        }

        // nodes 배열을 sum 합 순으로 내림차순 나열
        Collections.sort(nodes);

        // 가장 큰 sum 출력
        int result = nodes.get(0).sum;

        bw.write(result + "\n");
        bw.flush();
        bw.close();

    }

    public static class Node implements Comparable<Node> {
        public int num;
        public int sum;

        public Node(int num, int sum) {
            this.num = num;
            this.sum = sum;
        }

        @Override
        public int compareTo(Node n) {
            return n.sum - this.sum;
        }
    }
}