99클럽 코테 스터디 28일차 TIL DP(가장 큰 증가하는 부분 수열)

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

 

<아이디어>

어제와 비슷한 유형의 문제이다.

문제에서 구해야 하는 값을 dp배열에 저장하는 값으로 설정하고, 그 규칙을 하나씩 찾아봤다.

dp[0] 은 무조건 배열의 값일것이고, 그 뒤는 현재 값의 앞에 있는 값들을 탐색하면서 현재 값보다 작은 값이 있으면 그 값에 현재 값을 더한다.

그리고 이런 값들을 Math.max를 통해 최댓값으로 갱신하며 구하면 끝!

(자세한 건 아래 주석 참고)

** 참 저 ans 때문에 98%에서 또 틀렸는데, ans를 자꾸 습관적으로 0으로 초기화해서 1 1을 넣었을 때 0이 나왔다(반목문 안돌아서)

ans 초기화도 생각을 잘 해서 초기화하자.. 여기선 dp[0]으로..

 

<제출코드>

package Study.Week04;

/*
1 : dp[0] = 1
1 100 : dp[1] = dp[0] + 100
1 100 2 : dp[2] = dp[0] + 2
1 100 2 50 : dp[3] = Math.max(dp[0] + 50, dp[2] + 50)
 */

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

public class Day28_BOJ_11055_가장큰증가하는부분수열 {
    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[i] = arr[i];
        }
        // 또 여기서 실수함 ㅠ
        int ans = dp[0];

        for(int i=1; i<n; i++){
            for(int j=0; j<i; j++){
                // 이전 값에서 현재 값보다 작은 값이 있으면
                if(arr[j] < arr[i]) dp[i] = Math.max(dp[i], dp[j] + arr[i]);
            }
            ans = Math.max(ans, dp[i]);
        }
        System.out.println(ans);
    }
}