[백준] DP - 11053번, 가장 긴 증가하는 부분 수열 (다른 풀이 봄)

* 공부 목표

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

 

문) 수열 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)

---

풀이

1. 테이블 정의

• 입력 값 A만큼 반복 입력받고, Ai에 해당하는 배열을 저장하여 최대값 부분 수열 구하기

2. 점화식 : D[i] = D[j] +1;

3. 초기값 : D[i] = 1;

 

(예시) D[]에 들어가는 수열의 길이

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

즉, D[i]는 최소 1이상의 길이를 가지며,
현재값이 이전값보다 클 때 +1씩 누적시키면 됨.

 

코드

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));
        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[n];
        int[] d = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        for(int i=0; i<n; i++) {
            if(st.hasMoreTokens()) {
                arr[i] = Integer.parseInt(st.nextToken());
            }
        }
        for(int i=0; i<n; i++) {
            d[i] = 1; //자기 하나면 값이 1.
            for(int j=0; j<i; j++) {
                //이전의 원소가 현재값보다 작고, 현재 누적값(1)보다 이전 누적값+1이 더 클때
                if(arr[j] <arr[i] && d[i] < d[j] +1) {
                    d[i] = d[j] +1;
                }
            }

        }
        int max = 0;
        for(int i=0; i<n; i++) {
            max = d[i] > max ? d[i]:max;
        }
        br.close();
        System.out.println(max);
    }
}

---

맨 처음에는 포도주 시식 문제처럼 oxo, oox, xoo ... 경우의 수를 따져가며 구하려고 했음.

그런데 도저히 답이 안 나와서 고민했을 때,

이전과 현재 값 비교하며 1씩 누적시키면 된다는 부분을 캐치함.

 

낭패였던 점은, 최댓값 구하는 for문 안에서 dp도 함께 돌리려고 했던 것

그리고 중첩 for문을 생각하지 못했던 것.

순간 여러가지 사고가 섞여서 분별이 안 됐던 것 같다. ㅜㅜ

 

참고 https://st-lab.tistory.com/137