백준 14002 가장 긴 증가하는 부분 수열 4 동적계획법 활용 풀이 ( Java )

14002번: 가장 긴 증가하는 부분 수열 4

백준 11053 가장 긴 증가하는 부분 수열 동적계획법 활용 풀이 (Java)

위에서 푼 것과 비슷한 문제. 대신 수열 자체를 찍어줘야 했는데

처음엔 마지막 최대값이 바뀔 때마다 arrayList에 추가해서 그걸 찍어주는 방식으로 접근했는데

주어진 테스트 케이스 수행할 때는 정답이 나왔지만 제출하니 '틀렸습니다'가 떴다.

 

질문 글을 찾아보니 반례 케이스 ( 7 / 1 6 2 4 5 3 7 을 입력했을 때 5 / 1 2 4 5 7 이 나와야 한다 )가 있어서 넣고 돌려보니 실패 확인. 

 

- 틀렸던 코드

 

import java.io.*;
import java.util.ArrayList;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int n = Integer.parseInt(br.readLine());
 
        int[] a = new int[n];
        // 숫자들 저장할 배열
        int[] d = new int[n];
        // 증가하는 수열 길이 저장할 배열
        // d[i] = a[1], ~~ a[i] 까지 수열이 있을 때 a[i]를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이
 
        String[] words = br.readLine().split(" ");
 
        for (int i = 0; i < words.length; i++) {
            a[i] = Integer.parseInt(words[i]);
        }
        // split 해서 숫자를 넣는다
 
        for (int i = 0; i < n; i++) {
            // 0부터 n까지
            d[i] = 1;
            // 증가하는 수열 길이를 1로 놓고
            for (int j = 0; j < i; j++) {
                // 처음부터 i까지 비교하며
                if (a[j] < a[i] && d[i] < d[j] + 1) {
                    // a[i]가 a[j] 보다 크고 d[j] + 1 값이 d[i]보다 길면
                    d[i] = d[j] + 1;
                    // 증가하는 수열 길이를 증가시켜준다
                }
            }
        }
 
        int answer = 0;
 
        ArrayList<Integer> al = new ArrayList<Integer>();
        // 연속 수열 저장할 arraylist
        
        for (int i = 0; i < d.length; i++) {
            // d 배열에서
            if (answer < d[i]) {
 
                answer = d[i];
                al.add(a[i]);
                // 최대값과 증가하는 부분 수열 찾아서
            }
        }
 
        bw.write(String.valueOf(answer)+'\n');
        
        for(int i=0; i < al.size(); i ++) {
            bw.write(String.valueOf(al.get(i))+" "); 
        }
        // 출력
        bw.flush();
 
    }
 
}

 

결국 역추적 배열을 하나 만들어서 인덱스를 저장하고 따라가서 출력하는 방식으로 정답을 받았다

 

import java.io.*;
 
public class Main {
 
    static int[] a;
    // 숫자들 저장할 배열
    static int[] v;
    // 역추적에 활용할 배열
 
    static void go(int p, BufferedWriter bw) throws IOException {
        if (p == -1) {
            return;
        }
        go(v[p], bw);
        bw.write(String.valueOf(a[p]) + " ");
    }
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int n = Integer.parseInt(br.readLine());
 
        a = new int[n];
        v = new int[n];
        // 배열 메모리 할당
 
        int[] d = new int[n];
        // 증가하는 수열 길이 저장할 배열
        // d[i] = a[1], ~~ a[i] 까지 수열이 있을 때 a[i]를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이
 
        String[] words = br.readLine().split(" ");
 
        for (int i = 0; i < words.length; i++) {
            a[i] = Integer.parseInt(words[i]);
        }
        // words 를 split 해서 숫자를 넣는다
 
        for (int i = 0; i < n; i++) {
            // 0부터 n까지
            d[i] = 1;
            // 증가하는 수열 길이는 일단 1로 놓고
            v[i] = -1;
            // 역추적 배열은 일단 -1로 놓는다 ( 0부터 시작하니 )
            for (int j = 0; j < i; j++) {
                // 처음부터 i까지 비교하며
                if (a[j] < a[i] && d[i] < d[j] + 1) {
                    // a[i]가 a[j] 보다 크고 d[j] + 1 값이 d[i]보다 길면
                    d[i] = d[j] + 1;
                    // 증가하는 수열 길이를 증가시켜주고
                    v[i] = j;
                    // 역추적하기 위해 배열 인덱스 저장
                }
            }
        }
 
        int answer = 0;
        int p = 0;
 
        for (int i = 0; i < d.length; i++) {
            // d 배열에서
            if (answer < d[i]) {
                // 최대값이 바뀌는 순간마다
                answer = d[i];
                // 최대값과 저장하고
                p = i;
                // 제일 클 경우의 인덱스 젖아해서
            }
        }
 
        bw.write(String.valueOf(answer) + '\n');
        // 최대값 출력하고
 
        go(p, bw);
        // 재귀로 출력한다 증가하는 부분 수열 출력
        bw.flush();
 
    }
 
}