*백준 11053번 가장 긴 증가하는 부분 수열(자바) - dp

가장 긴 증가하는 부분 수열

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

256 MB

77659

30069

19783

36.979%

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1 복사

6

10 20 10 30 20 50

예제 출력 1 복사

4

---

이 문제는 너무 어렵게 생각해서 못풀어낸 문제였다. 

풀이 : 

 

일단 arr[0] = 10에서 10 이전 값은 없으므로 dp[0] = 1이다.

arr	10	20	10	30	20	50
dp	1

 

arr[1] = 20 보다 arr[0] 의 값이 더 작으므로 dp[1] = dp[0] + 1이다.

arr	10	20	10	30	20	50
dp	1	2

 

arr[2] = 10에서 arr[2]보다 작은 값을 갖는 arr이 없으므로 dp[2]=1이다.

arr	10	20	10	30	20	50
dp	1	2	1

 

arr[3]=30에서 arr[0]은 arr[3]보다 작으므로 dp[3] = dp[0]+1 = 2이다.

또, arr[1]도 arr[3]보다 작으므로 dp[3] = dp[1]+1이다.

arr[2]도 arr[3]보다 작은데 이 때 dp[3] = dp[2]+1을 해주면 dp[3]에 2가 저장되게 된다. 이런 오류를 막기 위해 dp[3]의 값이 dp[2]의 값보다 작을 경우에만 dp[3] = dp[2]+1 연산을 수행하도록 해줘야 한다.

즉, 이 경우 arr[1]과의 비교를 통해 dp[3]에 dp[1]+1 = 3이라는 값이 저장되어 있었고 

arr[2]=10 과 비교하는 과정에서 dp[3]=3 > dp[2]=1이므로 dp[3]에는 최종적으로 3을 저장하도록 해야 한다.

arr	10	20	10	30	20	50
dp	1	2	1	3

 

이렇게 어렵게 설명을 했지만 그냥 자신보다 이전의 값 중에서 자신의 arr값보다 작은 값을 갖는 것들을 찾아낸 후 그들의 dp 중에 가장 큰 값에 +1을 하여 자신의 dp값으로 저장을 하면 된다.

 

arr[4]=20의 경우 arr[0]과 arr[2]의 값이 자신의 값보다 작고, 이들의 dp값은 같으므로 dp[4]=1+1=2이다. 

arr	10	20	10	30	20	50
dp	1	2	1	3	2

 

dp[5]=50의 경우 모든 arr이 자신의 값보다 작으므로 dp[0]부터 비교해가며 dp값을 저장해나간다.

dp[5]=dp[0]+1=2가 되고, 그 후 dp[5]<=dp[1]이므로 dp[5]=dp[1]+1=3이 되고,

dp[5] > dp[2]이므로 dp[5]는 그대로 3의 값을 유지하고,

dp[5] <= dp[3]이므로 dp[5]=dp[3]+1=4가 되고, 

dp[5] > dp[4]이므로 dp[5]는 그대로 4를 유지한다.

arr	10	20	10	30	20	50
dp	1	2	1	3	2	4

 

---

import java.util.Scanner;


public class Main {
   static int arr[];
   static int dp[];
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        arr = new int[n];
        dp = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        int max = 1;
        for (int i = 0; i < arr.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i] && dp[i] <= dp[j]) {
                    dp[i] = dp[j] + 1;
                }
            }
            max = Math.max(max, dp[i]);
        }

        System.out.println(max);
    }
}