[백준] JAVA 자바 : 가장 긴 증가하는 부분 수열 4 (14002번)

---

다이나믹프로그래밍에서 처음 만난 골드 등급 문제…
이거 푸려고 몇 시간을 헤맸다… 분명 가장 긴 증가하는 부분 수열은 나쁘지 않게 풀렸는데 가장 긴 수열을 출력하는 부분이 상당히 오래 걸림…

나는 어떻게 풀었냐면 가장 길어지는 부분의 인덱스를 now라는 변수에 저장해 놓고, 가장 길어질 때마다 그 때의 인덱스로 now를 갱신했다.
그리고 외부 for문을 한 바퀴 돌 때마다 dp[now]와 현재의 dp[i]를 비교해서, dp[i]가 dp[now]보다 길다면 현재까지 가장 길었던 수열(sa[now])에 지금의 수 A[i]를 덧붙이고, 그렇지 않다면 sa[i]에는 A[i]부터 시작하는 새로운 수열을 담도록 했다.

나도 글로 쓰니까 무슨 말인지 제대로 이해가 안 되는데… 머릿속으로 그린 걸 글로 쓰는게 참 힘들긴 한가보다…

 

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

public class LongestIncreasingSequence_4 {

    static int[] dp;
    static int[] A;

    public static int stoi(String str) {
        return Integer.parseInt(str);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = stoi(br.readLine());
        A = new int[N+1]; // 수열 A

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i=1; i<=N; i++) {
            A[i] = stoi(st.nextToken());
        }

        dp = new int[N+1];
        dp[1] = 1;

        String[] sa = new String[N+1];
        sa[1] = Integer.toString(A[1]);

        int now = 1;
        for (int i=2; i<=N; i++) {
            dp[i] = 1;
            for (int j=1; j<i; j++) {
                if (A[i] > A[j]) {
                    if (dp[i] <= dp[j]) {
                        dp[i] = dp[j] + 1;
                        now = j;
                    }
                }
            }
            if (dp[i] > dp[now]) {
                sa[i] = sa[now] + " " + A[i];
            } else {
                sa[i] = Integer.toString(A[i]);
            }
        }

        int max = 0;
        int max_i = 0;
        for (int i=1; i<=N; i++) {
            if (max <= dp[i]) {
                max = dp[i];
                max_i = i;
            }
        }
        System.out.println(max);
        System.out.println(sa[max_i]);
    }
}

로그인

 

 

작성일자: 2024-01-05