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

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

---

문제

수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

---

접근

• 문제에서, '가장 긴'과, '증가하는', 이 두 부분에 초점을 맞춰야 한다. 
• 증가하기만 해서는 안되고, 길이 역시 체크해줘야 한다. 
• 예를 들어, [10, 20, 70, 30, 40, 50] 이라면, 정답은 [10, 20, 70]이 아닌, [10, 20, 30, 40, 50]이다. 
• dp를 1로 초기화한다. dp는 가장 긴 증가하는 수열의 길이가 들어간다. 
• list[i]와 list[j]를 비교하여, list[i]가 크다면, 이전까지의 dp중 가장 큰 것에 1을 더한 값을 현재 dp로 한다. 
• 입력값을 [10, 20, 10, 30, 20, 50]으로 했을 때의 dp는 다음과 같다. 

index	1	2	3	4	5	6
dp	1	2	1	3	2	4

• for문 안의 for문에서, "if (list[i] > list[j])"에 등호(=)가 들어가면, 실패한다. 이유는?

---

코드

package beak;
 
import java.io.*;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int n = Integer.parseInt(br.readLine());
 
        int[] list = new int[n + 1];
        int[] dp = new int[n + 1];
        int ans = 0;
 
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= n; i++) {
            list[i] = Integer.parseInt(st.nextToken());
            dp[i] = 1;
        }
 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                if (list[i] > list[j]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
        }
 
        for (int i = 1; i <= n; i++) {
            if (ans < dp[i])
                ans = dp[i];
        }
 
        bw.write(ans + "\n");
 
        bw.flush();
        br.close();
 
    }
}