백준 11055번 - 가장 큰 증가 부분 수열 (Java)

 

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

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

코드 :

dp - top down

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

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

        int N = Integer.parseInt(br.readLine());
        seq = new int[N + 1];
        dp = new int[N + 1];

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

        //dp[N]은 seq[N]이 어떤 부분수열의 가장 큰 수일때 해당 수열의 합
        dp[1] = seq[1];
        recur(N);
        int max = 0;
        for (int i = 1; i <= N; i++) {
            max = Math.max(max, dp[i]);
        }

        System.out.print(max);
    }

    public static int recur(int N) {
        if(dp[N] == 0){
            //초기화 안하면 왜 안됨?
            dp[N] = seq[N];
            for (int i = N-1; i >= 1; i--) {
                if (seq[i] < seq[N]) {
                    dp[N] = Math.max(recur(i) + seq[N], dp[N]);
                } else{
                    // N보다 i가 작지 않은 경우, 해당 수가 마지막 수라고 가정하고 수열 구하기
                    recur(i);
                }
            }
        }
        return dp[N];
    }
}

풀이 :

가장 큰 증가하는 부분 수열 시리즈라서 개념 자체는 어렵지 않았는데, recur함수에서 첫 값을 초기화 해주지 않았을때 계속 실패가 나와서 아래 블로그를 보고 참고했다.

 

recur함수에서 else부분을 구현하는 것도 아래 블로그를 보고 알았다. 그 전에는 그냥 for문 돌렸는데, 생각해보면 효율도 안좋고 보기도 별로였다.

참고 :

https://hongjw1938.tistory.com/71

알고리즘 풀이 - 백준 11055(가장 큰 증가 부분 수열, DP)