[백준] 11055번: 가장 큰 증가하는 부분 수열 - Java, 자바

문제접근

이 문제에서는 dp의 값으로는 해당 배열의 부분 수열의 합이 들어간다.
비교하려는 arr[N] 에 대하여 N - 1부터 arr[N]과 비교하여 값이 더 작을경우
dp[N] 에 dp[N] 과 dp[N - 1] + arr[N] 를 비교하여 더 큰 값을 dp[N] 에 할당한다.
예를들어, 처음 dp배열의 초기값은 입력받은 값들이 들어갈 것이다. 왜냐하면 수열의 합이 기본적으로 자기자신을 포함하기 때문이다.
다음으로는 for문을 돌면서 N 보다 작은 N-1 ~ 0 까지 순회하며 입력받은 arr값들을 비교한다. 만약 N과 비교하여 이전값들이 더 작다면 dp[N]에 dp[N]과 dp[해당 루프 값 (j)] + arr[N] 을 더해 더 큰 값을 dp[N]에 저장한다.

예제입력을 보면 dp배열의 초기값으로
dp[0] = 1;
dp[1] = 100;
dp[2] = 2;
dp[3] = 50;
dp[4] = 60;
dp[5] = 3;
dp[6] = 5;
dp[7] = 6;
dp[8] = 7;
dp[9] = 8;
이 들어가게 된다.

다음으로 한 예시로 만약 N = 5 일 때를 기준으로 bottom-up으로 for문을 돌면서 값을 구해보자.

for(int i = 0; i < N(5); i++) {
	dp[i] = number[i];
    for(int j = 0; j < i; j++) {
    	dp[i] = Math.max(dp[i], dp[j] + number[i]);
    }
}

• i=0 (1)

  • i가 0일때는 처음 초기값 설정 이후 내부 for문은 타지않는다. 따라서
  • dp[0] = 1;

• i=1 (100)

  • i=1 일때는 내부 for문을 타게되고, dp[0] + number[1] 과 dp[1] 중에 더 큰값을 저장하게 된다. 각각의 값은 101 과 100이다.
  • dp[1] = 101;

• i=2 (2)

  • i=2 일때는 내부 for문으로는 0,1을 순회하며, number[1]은 조건에 맞지 않아 패스하게 되며, dp[0] + number[2] 과 dp[2]를 비교하게 된다.
  • dp[2] = 3;

• i=3 (50)

  • i=3 일때는 0~2를 순회하며, 조건에 맞는 0과 2를 비교하게 된다. 각각 dp[0] + number[3] 과, dp[2] + number[3]을 비교하게 되며 각각의 값은 51과 53이다.
  • dp[3] = 53;

• i=4 (60)

  • i=4 일때는 0~3를 순회하며, 조건에 맞는 0,2,3 을 비교하게 된다. 각각 dp[0] + number[4] 과, dp[2] + number[4], dp[3] + number[4]을 비교하게 되며 각각의 값은 51과 53, 113이다.
  • dp[4] = 113;

dp[0] = 1;
dp[1] = 101;
dp[2] = 3;
dp[3] = 53;
dp[4] = 113;
dp[5] = 6;
dp[6] = 11;
dp[7] = 17;
dp[8] = 24;
dp[9] = 32;

전체코드

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

public class Main {

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

        N = Integer.parseInt(br.readLine());
        number = new int[N];
        dp = new Integer[N];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        for(int i = 0; i < N; i++) {
            number[i] = Integer.parseInt(st.nextToken());
        }

        dp[0] = number[0];
        bottom_up_lis();

//        for(int i = 1; i < N; i++) {
//            recur_lis(i);
//        }

        int max = Integer.MIN_VALUE;

        for(int i = 0; i < N; i++) {

            if(max < dp[i]) {
                max = dp[i];
            }
        }

        System.out.println(max);
    }

    private static int recur_lis(int N) {

        if(dp[N] == null) {
            dp[N] = number[N];

            for(int i = N - 1; i >= 0; i--) {

                if(number[N] > number[i]) {
                    dp[N] = Math.max(dp[N], number[N] + recur_lis(i));;
                }
            }
        }

        return dp[N];
    }


    private static void bottom_up_lis() {

        for(int i = 1; i < N; i++) {
            dp[i] = number[i];

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