[BOJ]14002번: 가장 긴 증가하는 부분 수열 4(java)

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

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

 

 

방법 1: Top-down

import java.io.*;
import java.util.StringTokenizer;
 
public class Main {
 
    public static int[] arrNumbers;
    public static int[] arrMax;
    public static int[] arrSerial;
 
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            int iLength = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
            arrNumbers = new int[iLength];
            arrMax = new int[iLength];
            arrSerial = new int[iLength];
 
            int index = 0;
            while (st.hasMoreTokens()) {
                arrNumbers[index++] = Integer.parseInt(st.nextToken());
            }
 
            calculate(iLength - 1);
 
            int iMaxResult = arrMax[0];
            int iLastSerial = 0;
            for (int i = 0; i < iLength; i++) {
                if (iMaxResult < arrMax[i]) {
                    iMaxResult = arrMax[i];
                    iLastSerial = i;
                }
            }
 
            bw.write(iMaxResult + "\n");
            bw.write(serial(iLastSerial));
            bw.flush();
 
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
 
    public static void calculate(int i) {
        arrSerial[i] = -1;
        arrMax[i] = 1;
 
        if (i <= 0) {
            return;
        }
 
        calculate(i - 1);
 
        for (int j = 0; j < i; j++) {
            if (arrNumbers[j] < arrNumbers[i] && arrMax[i] < arrMax[j] + 1) {
                arrMax[i] = arrMax[j] + 1;
                arrSerial[i] = j;
            }
        }
    }
    
    public static String serial(int iNow) throws Exception {
        
        if (iNow < 0) {
            return "";
        }
        int iFormer = arrSerial[iNow];
 
        return serial(iFormer) + arrNumbers[iNow] + " ";
    }
}

 

방법 2: Bottom-up

import java.io.*;
import java.util.StringTokenizer;
 
public class Main {
 
    public static int[] arrNumbers;
    public static int[] arrSerial;
 
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            int iLength = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            
            arrNumbers = new int[iLength];
            arrSerial = new int[iLength];
            int[] arrMax = new int[iLength];
            
            for (int i = 0; i < iLength; i++) {
                arrNumbers[i] = Integer.parseInt(st.nextToken());
            }
            
            int iResultMax = 0;
            int iLastSerial = 0;
            
            for (int i = 0; i < iLength; i++) {
                
                arrMax[i] = 1; 
                arrSerial[i] = -1;
                for(int j = 0; j < i; j++) {
                    if (arrNumbers[j] < arrNumbers[i] && arrMax[i] < arrMax[j] + 1) {
                        arrMax[i] = arrMax[j] + 1;
                        arrSerial[i] = j;
                    }
                }
                
                if (iResultMax < arrMax[i]) {
                    iResultMax = arrMax[i];
                    iLastSerial = i;
                }
            }
            
            bw.write(iResultMax+ "\n");
            bw.write(serial(iLastSerial));
            bw.flush();
            
            
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
 
    public static String serial(int iNow) throws Exception {
        if (iNow < 0) {
            return "";
        }
        int iFormer = arrSerial[iNow];
 
        return serial(iFormer) + arrNumbers[iNow] + " ";
    }
}

탑다운이 메모리는 덜먹었지만 바텀업이 조금 더 빨랐다. 

 

 

TIP1

가장 긴 증가하는 부분 수열 문제에서

"가장 긴 증가하는 부분 수열 출력하기"가 더해진 문제이다.

 

①

int[] arrSerial 배열을 하나 더 만든 후,

가장 마지막으로 조건문을 충족한 수열 A[ j ] 의 위치값 j를

arrSerial[ i ] 에 저장하자

arrMax[i] = 1; 
arrSerial[i] = -1;
 
for(int j = 0; j < i; j++) {
    if (arrNumbers[j] < arrNumbers[i] && arrMax[i] < arrMax[j] + 1) {
        arrMax[i] = arrMax[j] + 1;
        arrSerial[i] = j;
    }
}

 

 

②

arrSerial 배열에 저장시킨 이전 수열의 값을 역순차적으로 불러낸다.

public static String serial(int iNow) throws Exception {
    if (iNow < 0) {
        return "";
    }
    int iFormer = arrSerial[iNow];
 
    return serial(iFormer) + arrNumbers[iNow] + " ";
}