BOJ) 가장 큰 증가 부분 수열

가장 큰 증가 부분 수열

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

풀이

 

다이나믹 프로그래밍 문제는 너무 어렵다.. ㅠㅠ

다른 문제 유형보다 생각을 조금 많이 요한다.

많은 실패를 겪고 답을 찾았다.

 

먼저, 각 index에서 취할 수 있는 가장 큰 증가 부분 수열의 합을 저장할 dp를 선언해준다.

이후 for문을 통해 index를 탐색하면서( i ) dp[i] 에 최대값을 저장한다.

최대값을 저장하는 과정은 0부터 해당 index 전 까지 for문을 돌면서 ( j ), 

i 번째 숫자보다 j 번째 숫자가 작은 경우에 수식을 진행한다.

수식은 dp [i]와 dp[j] + i 숫자로 진행을 해준다.

j 까지 가장 큰 부분 수열의 합에 i번 째 수를 더해주는 것이다.

 

풀고나면 굉장히 간단해보이지만, 답을 도출하기까지 가장 오래 걸리는 ? 유형중에 하나인 것 같다.

dp문제를 좀 더 풀어봐야겠다.

 

코드

 

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());
        int[] numArr = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++) {
            numArr[i] = Integer.parseInt(st.nextToken());
        }
        br.close();
        solution(n, numArr);
    }

    private static void solution(int n, int[] numArr) {
        int answer =0;
        int[] dp = new int[n];
        for(int i=0; i<n; i++) {
            dp[i] = numArr[i];
            for(int j=0; j<i; j++) {
                if(numArr[i] > numArr[j]) {
                    dp[i] = Math.max(dp[j] + numArr[i], dp[i]);
                }
            }
            answer = Math.max(answer, dp[i]);
        }
        System.out.println(answer);
    }
}