백준 11053번 : 가장 긴 증가하는 부분 수열 자바

 

 

 

🧫 문제 분석

 

✔️ 출처

가장 긴 증가하는 부분 수열 실버 2

 

📖 문제

 

DP 문제로 

현재 값이 이전 값보다 크다면 이전 값의 수열 개수와 현재 값의 수열 개수중 더 큰 값을 취하면 된다. 

 

// j = i - 1 ~ 0까지
if (arr[j] < arr[i]) {
    dp[i] = Math.max(dp[j], dp[i]);
}

 

문제의 예시로 

현재 4번째 30이라고 하자

 

10 < 30 이므로 dp[3] 과 dp[4] 의 값 중 더 큰 값을 취한다. 

dp[4]는 처음 값은 0이므로 dp[3]의 값을 가진다. dp[3]은 1이다. (3번째 10은 이전에 증가하는 수열이 없고 10밖에 없음)

그다음 2번째 20 < 30 이므로 dp[2], dp[4] 의 값중 더 큰 값을 취한다.

dp[2] 는 2이므로 dp[4] = 2이고 

이 연산이 끝나면 dp[4]에 30도 카운팅해주면 3이된다. 

 

 

이 풀이에서 중요한 것은 수열의 크기가 1일 때는 수열의 길이도 1이라는 것이다.

 

 

 

---

🔅 문제 풀이

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    static int[] dp;
    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[] arr = new int[n+1];
        int max = 1; // 주어진 수열의 길이가 1일 경우에 1을 출력하기 위함
        dp = new int[n+1];

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

        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            for (int j = i - 1; j >= 1; j--) {
                if (arr[j] < arr[i]) {
                    dp[i] = Math.max(dp[j], dp[i]);
                }
            }
            dp[i]++;
            max = Math.max(dp[i], max);
        }

        bw.write(max +"");
        bw.flush();
        bw.close();
    }
}// 코드 내용

 

 

 

❗ 오답노트 / 필요한 지식

1. 반례를 찾는 것도 중요하다.