[TIL] 99클럽 코테 스터디 28일차 TIL + 백준 11055 가장 큰 증가하는 부분 수열

문제 풀이

 

문제 탐색하기

이 문제는 DP 알고리즘을 통해서 풀 수 있습니다.

비슷한 유형의 문제(백준 11722 가장 긴 감소하는 부분 수열)를 앞 게시글에서 풀 수 있었습니다. 

 

따라서 DP알고리즘의 개념에 대해서는 아래 게시글에 작성해두었습니다.

https://coding-babo.tistory.com/173

[TIL] 99클럽 코테 스터디 27일차 TIL + 백준 11722 가장 긴 감소하는 부분 수열

 

DP 알고리즘을 통해 문제 풀이를 구현해 보자면 아래와 같습니다.

1. 수열을 저장할 int[] 배열과 dp 알고리즘을 통해서 값을 저장할 int[] 배열을 선언합니다.
2. 선언한 dp 배열의 첫번째 원소를 수열의 첫번째 원소로 초기화 합니다.
3. 수열 배열을 탐색하며 현재 값의 이전 값들을 비교해서 현재 값보다 작은 값이 나온다면 그 때의 dp 배열의 값과 현재 수열의 값의 합이 현재의 dp 배열의 값을 비교하여 더 큰 값으로 현재 dp 배열의 값을 재세팅 해줍니다.
4. 탐색이 종료되면 dp 배열 중 최대 값을 출력해줍니다.

 

문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
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());

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

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

        dp[0] = arr[0];

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

        int max = 0;
        for(int i : dp){
            max = Math.max(i, max);
        }

        System.out.println(max);
    }
}