[BOJ]11053번: 가장 긴 증가하는 부분 수열(java, c++)

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

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

 

방법 1: Top-down

import java.io.*;
import java.util.StringTokenizer;
 
public class Main {
 
    public static int[] arrNumbers;
    public static int[] arrMax;
 
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int iLength = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
            arrNumbers = new int[iLength];
            arrMax = new int[iLength];
 
            int index = 0;
            while (st.hasMoreTokens()) {
                arrNumbers[index++] = Integer.parseInt(st.nextToken());
            }
 
            calculate(iLength - 1);
 
            int iMaxResult = 0;
            for (int i = 0; i < iLength; i++) {
                iMaxResult = Math.max(iMaxResult, arrMax[i]);
            }
 
            System.out.println(iMaxResult);
 
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
 
    public static int calculate(int i) {
 
        if (i <= 0) {
            arrMax[i] = 1;
            return 1;
        }
 
        if (arrMax[i] > 0) {
            return arrMax[i];
        }
 
        calculate(i - 1);
 
        arrMax[i] = 1;
        
        for (int j = 0; j < i; j++) {
            if (arrNumbers[j] < arrNumbers[i] && arrMax[i] < arrMax[j] + 1) {
 
                arrMax[i] = arrMax[j] + 1;
            }
        }
 
        return arrMax[i];
    }
}

 

방법 2: Bottom-up

import java.io.*;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int iLength = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            
            int[] arrNumbers = new int[iLength];
            int[] arrMax = new int[iLength];
            
            for (int i = 0; i < iLength; i++) {
                arrNumbers[i] = Integer.parseInt(st.nextToken());
            }
            
            int iResultMax = 0;
            
            for (int i = 0; i < iLength; i++) {
                
                arrMax[i] = 1; 
                for(int j = 0; j < i; j++) {
                    if (arrNumbers[j] < arrNumbers[i] && arrMax[i] < arrMax[j] + 1) {
                        arrMax[i] = arrMax[j] + 1;
                    }
                }
                
                if (iResultMax < arrMax[i]) {
                    iResultMax = arrMax[i];
                }
            }
            
            System.out.println(iResultMax);
            
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

 

c++소스

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    // 입력
    int n;
    cin >> n;
 
    vector<int> A(n);
    for (int i = 0; i < n; i++)
    {
        cin >> A[i];
    }
    
    // LIS 수열의 사이즈 구하기
    // 점화식 : D[i] = max(D[j]) + 1 (j < i && A[j] < A[i] 일 때)
    vector<int> size(n);
    for (int i = 0; i < n; i++)
    {
        size[i] = 1;
        for (int j = 0; j < i; j++)
        {
            if (A[j] < A[i] && size[j] + 1 > size[i])
            {
                size[i] = size[j] + 1;
            }
        }
    }
 
    // 가장 긴 길이 출력
    cout << *max_element(size.begin(), size.end()) << '\n'; 
 
    return 0;
}

 

바텀업이 더 빨랐다

모든 수열을 차례대로 훑고 지나가는 문제는 바텀업이 더 빠른 것 같다.

 

 

TIP1

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에
가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

①

수열 A[1], A[2], ... A[N] 이 주어졌을 때,

이중에서 가장 오래동안 증가하는 수열을 찾아 길이를 구해야 한다. 

이를 D[N] 이라 하자. 

 

※ 생각의 흐름이 기본적으로 여기서부터 출발해야 하는 것 같다.

A[1] ~ A[N] 에서 무언가를 뽑아낸 수열을 D[N] 이라 하자.

계속 A[N] ~ A[끝값] 을 D[N]로 했다가 틀렸다. 카드 구매하기 문제의 교훈...

 

 

②

증가하는 수열이므로, 

A[k] < A[N]  ( 1 ≤ k ≤ N - 1 ) 일 때에만 D[N] 을 증가시킬 수 있다. 

 

 

③

수열 A = {10, 20, 10, 30, 20, 50}  에서 D[4]를 구할 때

A[2] 와 비교하면 A[2] < A[4] , D[2] = 2 이므로 D[4] = 3  

A[3] 와 비교하면 A[3] < A[4] , D[3] = 1 이므로 D[4] = 2 이다. 

 

따라서 D[N] <  D[k] + 1  ( 1 ≤ k ≤ N - 1 ) 일때에만 D[N] 을 증가시킬 수 있다. 

 

 

TIP2

가장 긴 증가하는 수열의 끝이 꼭 A[끝값] 이 아닐 수 있다!