[JAVA] 백준 11055번 - 가장 큰 증가 부분 수열

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

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

---

dp...

dynamic programming...

분명 점화식 꽤나 잘 세웠던 나였는데...

몇개월 안했다고 바아로 까먹는 나였다...

이거 사실 어제 푼건데 지금 정리나 하려고 하핫

 

 

 

자바 코드)

import java.util.Scanner;

import static java.util.Collections.max;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        int[] dp = new int[n];

        for(int i=0;i<n;i++) {
            arr[i] = scanner.nextInt();
        }

        int max = 0;
        for(int i=0;i<n;i++) {
            dp[i] = arr[i];
            for(int j=0;j<i;j++) {
                if(arr[i]>arr[j] && dp[i] < dp[j] + arr[i]) {
                    dp[i] = dp[j] + arr[i];
                }
            }
            max = Math.max(max, dp[i]);
        }
        System.out.println(max);
    }
}

주요 코드는 이중 for문 안의 코드이다

각 배열원소의 증가부분수열의 합을 저장하는 배열인 dp와 숫자를 저장하는 배열인 arr을 이용한다

arr 원소가 이전 원소보다 크고, dp의 현재 원소보다 arr과 dp 더한 값이 더 크면 그걸 업데이트 하는 방식으로 구했다

음.. 사실 아리까리하긴 한데 비슷한 거 더 풀다보면 금방 할듯!!