[PS] 백준 11053번 가장 긴 증가하는 부분 수열 - DP

문제

예제

풀이

이 풀이를 참고하였다. 이해하기 쉽게 그림까지 있고 잘 정리된 포스팅이어서 겨우 이해했다 ^^..

​

먼저 arr 배열에 입력 값을 넣는다.

반복문으로 dp[2]부터 dp[n]까지 1씩 위치를 이동(i = 2~n)해가며 dp배열에 가장 긴 수열의 길이를 저장할 것이다.

dp[1]은 초기 시작지점이므로 1로 초기화한다. 또한 출력할 최대값을 저장할 변수를 1로 초기화 해두고 시작한다.

맨처음값 부터 검증위치(i) 이전까지 arr 배열을 탐색(j)할 것이므로 이중 반복문을 돌린다.

i는 증가수열이 될 수 있는지 검증할 위치의 값이고,
j는 1부터 i의 이전위치까지 탐색하기 위한 값이다.

​

우선 dp[검증위치]값에 1을 저장해둔다.

• 탐색값보다 검증값이 크고
• 검증dp값(누적될 것임)이 현재dp값과 같거나 작으면

위 조건을 만족하면 dp[탐색위치] +1 한 값을 dp[검증위치]에 저장한다.
아니라면 dp[현재위치]값에는 1이 저장된채로 i++을 한다.

최대값과 dp[현재위치]값을 비교해서 큰값을 최대값으로 저장한다.

arr[6] = {10, 20, 10, 30, 20, 50} 의 배열이 있다고 할 때

arr = {10, 20} / i=2, j=1  
arr = {10, 20, 10} / i=3, j=1,2  
arr = {10, 20, 10, 30} / i=4, j=1,2,3  
arr = {10, 20, 10, 30, 20}  
arr = {10, 20, 10, 30, 20, 50}

i=4의 예시를 들어보자.
먼저 dp[4] =1을 셋팅한다.

j=1, i=4 :
arr[1]=10 < arr[4]=30 && dp[1]=1 >= dp[4]=1
→ dp[4]=dp[1]+1

검증dp값에 1~j까지 가장 긴 수열의 길이(10 -> 1) +1을 해주어 누적값을 만든다.

j=2, i=4 :
arr[2]=20 < arr[4]=30 && dp[2]=2 >= dp[4]=2
→ =dp[4]=dp[2]+1

똑같이 (10,20 -> 2) +1

코드

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

public class Main {

    public static void main(String[] args) throws NumberFormatException, IOException {

        Scanner in = new Scanner(System.in);

        int n = in.nextInt();

        int[] arr = new int[n+1];//값
        int[] dp = new int[n+1];//dp[탐색길이]에 가장 긴 수열의 길이 저장

        dp[1] = 1; //초기 시작지점은 1
        int max = 1;

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

        for(int i=2; i<=n; i++) {
            dp[i] = 1;

            for(int j=1; j<i; j++) {//1부터 현재위치까지 탐색

                //dp를 arr[1]부터 비교하면서 초기화
                if(arr[i] > arr[j] && dp[i] <= dp[j]) { 
                    dp[i] = dp[j] +1; //길이 +1 누적
                }
            }
            max = Math.max(max,dp[i]); //최대값과 비교
        }

        System.out.println(max);

    }
}