[Java] 11055번: 가장 큰 증가하는 부분 수열 Silver 2

문제 링크

이 문제는 잘 안 풀려서 예전에 풀었던 11053번: 가장 긴 증가하는 부분 수열에서 힌트를 얻었다 ㅋㅋ..

이 문제는 이중 for문을 통해서 앞에서 뒤로 가면서 해당 값에서 다음 수로 증가하는 수열이라면,
해당 위치에서 갱신돼 있던 최대 길이 + 1의 값과 기존의 최대 길이중
더 큰 값을 채택하면서 점점 누적해가는 방법으로 풀었다.

당시에는 파이썬으로 풀었는데, 코드를 보면 이렇다.

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
dp = [1] * n

for i in range(n - 1):
    for j in range(i + 1, n):
        if arr[i] < arr[j]:
            dp[j] = max(dp[j], dp[i] + 1)
            
print(max(dp))

정확히 이 방식을 사용했다고 할 순 없는데, 2중 for문으로 풀었다.

지금 문제도 마찬가지로 N이 최대 1000이라서 시간을 초과할 것 같지 않았다.
그래서 이 문제도 2중 for문으로 푸는 방법을 한 번 생각을 해봤다.
뒤에서부터 하나씩 위치를 고정 시키고,
뒤의 값들을 살펴보면서 최대 증가수열 합을 갱신시키는 방식으로 구현했다.

그러니까 위치를 하나 고정 시켰을 때,
뒤에 있는 어떤 값들과 수열을 이어야 최댓값이 되는지 알 수 없기 때문에
그냥 모든 케이스를 고려해보는 것이다..

그래서 이게 사실 맞기는 했지만,
이게 과연 DP방식이 맞는지 잘 모르겠다..

정답

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));

        // N 입력 받기
        int N = Integer.parseInt(br.readLine());

        // 수열 입력 받기
        int[] arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // dp
        int maxSum = 0;
        int[] dp = new int[N];
        for (int now = N - 1; now >= 0; now--) {
            dp[now] = arr[now];
            for (int next = now + 1; next < N; next++) {
                if (arr[now] < arr[next]) {
                    dp[now] = Math.max(dp[now], arr[now] + dp[next]);
                }
            }
            maxSum = Math.max(maxSum, dp[now]);
        }

        // 출력
        System.out.println(maxSum);
    }
}

근데 또 실행시간은 빠른 편이긴 하다..
N이 작아서 그럴 수도.. N이 커지면 시간 차이가 많이 날 수도 있으니까..

제일 빠른 코드의 로직을 한 번 배워보자..!

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));

        // N 입력 받기
        int N = Integer.parseInt(br.readLine());

        // 수열 입력 받기
        int[] arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }


        // 초기값 설정
        int[] dp = new int[N];
        for (int i = 0; i < N; i++) {
            dp[i] = arr[i];
        }

        // DP 수행 (앞에서부터 진행)
        int maxSum = dp[0];
        for (int now = 1; now < N; now++) { // 현재 위치
            for (int before = 0; before < now; before++) { // 이전 위치
                if (arr[before] < arr[now]) { // 증가하는 부분 수열 조건
                    dp[now] = Math.max(dp[now], dp[before] + arr[now]);
                }
            }
            maxSum = Math.max(maxSum, dp[now]); // 최대값 갱신
        }


        // 출력
        System.out.println(maxSum);
    }
}

이게 보편적인 풀이 방식인데, 음.. 내 방식(뒤에서 앞으로)이랑 방향만 정반대고 완전히 똑같은 로직이었다!!!

결국 내가 DP식으로 잘 푼게 맞았다..! 👏👍👍👍

아 그리고 점화식은 이렇다.

이제 실버2 문제는 끝이다!