BOJ11053 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053 (opens new window)

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구한다.

제출 코드

dp 테이블을 활용하여 해당 index까지 가장 긴 길이를 저장한다. 또한 자기 자신을 포함하기 때문에 적어도 1의 길이를 가질 것을 보장한다.

다음은 탐색하고자 하는 index i 이전 까지 증가하는 부분에서 이전 보다 긴 길이를 가지고 있다면 갱신하여 최댓값을 저장한다.

for (int i = 0; i < n; i++) {
    dp[i] = 1;

    for (int j = 0; j < i; j++) {
        if (numbers[j] < numbers[i]) {
            dp[i] = Math.max(dp[i], dp[j] + 1);
        }
    }
}

갱신한 dp 테이블 중 가장 큰 값을 꺼내어 출력하고 마무리한다.

아래는 최종 제출 코드이다.

public class BOJ11053 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[] numbers = new int[n];
        int[] dp = new int[n];

        for (int i = 0; i <  n; i++) {
            numbers[i] = scanner.nextInt();
        }

        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (numbers[j] < numbers[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        int max = Arrays.stream(dp)
                .max()
                .orElse(0);
        System.out.println(max);
    }
}

#algorithm #BOJ #다이나믹 프로그래밍