[백준] Silver II. 가장 긴 증가하는 부분 수열

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

 

사용 알고리즘

• 다이나믹 프로그래밍

 

풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/*
    테이블: d[i]: i번째 원소를 마지막으로 가지는 수열의 길이
    점화식: d[i] = max(d[i], d[j] + 1)
 */
public class Main {
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        int[] arr = new int[n + 1];
        int[] d = new int[n + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        for(int i = 1; i <= n; i++) { // 초기화 자기 자신만으로 부분 수열 구성 가능
            d[i] = 1;
        }

        int max = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j < i; j++) {
                if (arr[i] > arr[j]) {
                    d[i] = Math.max(d[i], d[j] + 1);
                }
            }
            max = Math.max(max, d[i]);
        }
        System.out.println(max);
    }
}

 

회고

 

테이블

• d[i]: i번째 숫자를 마지막으로 가지는 수열의 길이

점화식

• d[i] = Math.max(d[i], d[j] + 1), (1 <= j < i)

 

배열 d에 대해서 먼저 이해하고 문제를 풀어야 하는데, 테이블에서 정했듯이 수열의 길이를 저장한다.

 

이렇게 수열 A가 주어질 때,

10

20

10

30

20

50

 

배열 d는 이런식으로 초기화를 해주어야 한다.

1

1

1

1

1

1

 

수열은 무조건 자기 자신을 원소로 가지기 때문에, 값을 1로 초기화 해준다.

 

 

이중 포문을 돌때, 처음에 10을 볼 때는 길이가 1이 들어가고 20을 볼 때는 앞에 10보다 크므로 2가 저장된다.

1

2

 

 

 

이런식으로, 수열 끝까지 순회하다보면

1

2

1

3

2

4

 

 

d[i]: i번째 숫자를 마지막으로 가지는 수열의 길이를 올바르게 저장하게 된다. 결과값으로는 최댓값을 리턴해주면 된다