[java 백준] 실버 2/11053번 가장 긴 증가하는 부분 수열

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

11053번: 가장 긴 증가하는 부분 수열

import java.util.Scanner;
 
public class Main {
 
    public static int n;
 
    public static int[] arr;
    public static int[] dp;
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new int[n + 2];
        dp = new int[n + 2];
 
        for (int i = 0; i < n; i++) {
 
            arr[i] = sc.nextInt();
 
        }
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            dp[i]=1; //초기화 
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
 
                }
 
            }
        }
 
        int max = 0;
        for (int i = 1; i <= n; i++) {
            if (max < dp[i]) {
                max = dp[i];
            }
        }
        System.out.println(max);
 
    }
 
}

 

처음 생각했던 코드

---

처음 생각했던 코드는 아래와 같았다.

import java.util.Scanner;
 
public class Main {
 
    public static int n;
 
    public static int[] arr;
    public static int[] dp;
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new int[n + 2];
        dp = new int[n + 2];
        int count = 0;
        for (int i = 1; i <= n; i++) {
 
            arr[i] = sc.nextInt();
 
        }
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
 
            if (arr[i] > arr[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            } else {
                dp[i] = dp[i - 1];
            }
        }
        System.out.println(dp[n]);
    }
 
}

이 경우 문제점은 arr[0]=10,arr[1]=20,arr[2]=10 일때, dp[2]=1이여야 하는데, dp[2]=2가 된다.

https://developer-mac.tistory.com/71

[Java]백준 11053번 :: 가장 긴 증가하는 부분 수열

위 링크에 그 이유가 잘 설명되어 있다.

숫자가 작아지면 해당숫자의 dp값이 1 작아진다는 것을 생각하지 못했다.

그래서 2차원 배열로 풀었다!

 

풀면서 중요한 부분

---

 

 

dp[0] = 1;
for (int i = 1; i <= n; i++) {
     dp[i]=1; //초기화 
     for (int j = 0; j < i; j++) {
          if (arr[j] < arr[i]) {
               dp[i] = Math.max(dp[j] + 1, dp[i]);
           }
     }
}
 

i가 2이고,j가 0일때 arr[0]<arr[2] 조건을 만족시키지 않는다. 이런 경우처럼 조건을 만족시키지 않을 때, dp[i]값을 유지시켜줘야 하므로 3번째줄 처럼 dp[i]=1로 초기화하는 것이 필요하다.

i가 2이고 j가 1일 때 arr[1]<arr[2] 조건을 만족시키지 않는다. 그러므로 dp[2]=1이다.

 

i가 3이고, j가 0일 때, arr[0]<arr[3]을 만족시키므로 

dp[3]은 dp[0}+1과 dp[3] 중에 큰 것은 2와 1중에 큰 것을 비교하는 것이므로 dp[3]=2이다.

 

i가 3이고j가 1일 때 또한 조건을 만족시키므로 (20<30)

dp[3]은 dp[1]+1과 dp[3] 즉, 2와 3중에 큰 것이므로 dp[3]=3이 된다. 

 

i가 3이고 j이가 2일 때도 조건을 만족시키므로 (10<30)dp[2]+1과 dp[3] 즉 2와 3 중에 큰 것이므로 dp[3]=3이 된다.