문제링크

https://www.acmicpc.net/problem/11055

구현방법

가장 긴 증가하는 부분수열에서 조금 바뀐 버전으로 dp를 통해서 값을 계산할 수있습니다.

각 idx에 자신들의 값을 넣어두고 현재 idx 기준으로 0 ~ idx-1까지 값들을 차례로 돌아가면서 idx위치의 값보다 작은 경우에 현재 dp의 값과 dp에 list의 비교값을 더한 값중 더큰 값으로 갱신을 진행해줍니다.

그들의 합도 현재 idx와 지금까지 갱신하면서 진행된 sum값과 비교하면서 최대값을 갱신시켜줍니다.

증가하는 부분 수열에 관해서 확실하게 아는 듯하였는데 꽤 많은 고민이 필요했고 거기에 참고도 하였습니다. 좀 더 풀어봐야 할것같습니다. 최근에 다른 걸 해보다 보니 다시 복기할 필요성이 느껴집니다.

참고 블로그 :

https://kjs-dev.tistory.com/entry/%EB%B0%B1%EC%A4%80-%EC%9E%90%EB%B0%94-11055-%EA%B0%80%EC%9E%A5-%ED%81%B0-%EC%A6%9D%EA%B0%80-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4

구현알고리즘

다이나믹프로그래밍(DP)

CODE

package com.backjoon.Silver.p11055;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int list[] = new int[N];
        int dp[] = new int [N];
        for(int idx = 0; idx <N;idx++){
            list[idx] = Integer.parseInt(st.nextToken());
            dp[idx] = list[idx];
        }

        int sum = dp[0];
        for(int idx = 0; idx < N; idx++){
            for(int next= 0;next <idx;next++){
                if(list[next] < list[idx]){
                    dp[idx] = Math.max(dp[next]+list[idx],dp[idx]);
                    sum = Math.max(sum,dp[idx]);
                }
            }

        }
        System.out.println(sum);
    }
}