[백준] 간식 파티 (자바)

간식 파티

풀이 방법

오름차순으로 가장 큰 합을 가지는 DP 배열을 만드는 문제다

1. 초기 DP 배열 값은 입력된 배열 값과 동일하게 설정
2. 이중 for문으로 오름차순을 가지는 배열값(arr[i])이 나오면 dp[i] = Math.max(dp[i], dp[j] + arr[i])

구현 코드

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

import java.lang.*;

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));

        int num = Integer.parseInt(br.readLine());

        int[] arr = new int[num];
        int[] dp = new int[num];


        for (int i = 0; i < num; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        for (int i = 0; i < num ; i++){
            dp[i] = arr[i];
            for (int j = 0; j < i; j++){
                if (arr[i] > arr[j]){
                    dp[i] = Math.max(dp[i], dp[j] + arr[i]);
                }
            }
        }

        Arrays.sort(dp);

        bw.write(dp[num-1]+"");

        bw.flush();
        br.close();
        bw.close();
    }


}