백준 11053번
https://www.acmicpc.net/problem/11053

문제

---

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

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

생각하기

---

• Top-Down(재귀) 방법으로 구현

• memoization 배열에 본인 같은 인덱스위치arr[]보다 작은 숫자의 갯수를 넣음
  (memo[] 배열은 증가하는 부분수열의 값을 넣는 배열임)

• 결론은 증가하는 부분수열 길이의 누적합을 memo에 저장함

동작

		for(int i=0; i<A; i++) {
			DP(i);
		}

arr 배열 길이만큼 DP메소드를 실행해서 탐색함.

	private static int DP(int N) {
		if(memo[N] == null) {
			memo[N] = 1;

			for(int i=N-1; i>=0; i--) {
				if(arr[i] < arr[N]) {
					memo[N] = Math.max(memo[N], DP(i)+1);					
				}
			}
		}

		return memo[N];
	} // End of DP

N값을 기준으로 1, 2..1, 3..1, 4..1, 형식으로 계속 반복해서 전체memo 배열을 만들어냄

arr[N] 기준으로 본인보다 작은 값이 있다면, 기존에 있던 값에서 +1을 하여
계속해서 max값을 갱신하고 memo값을 갱신하는 방법이다.

코드

---

Java

import java.util.*;
import java.io.*;

public class Main {
	static Integer memo[];
	static int arr[];

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

		int A = Integer.parseInt(br.readLine()); 
		memo = new Integer[A];
		arr = new int[A];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<A; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		//Arrays.sort(arr);

		for(int i=0; i<A; i++) {
			DP(i);
		}

		int max = memo[0];
		for(int i=1; i<A; i++) {
			max = Math.max(max,  memo[i]);
		}

		System.out.print(max);
	} // End of main

	private static int DP(int N) {
		if(memo[N] == null) {
			memo[N] = 1;

			for(int i=N-1; i>=0; i--) {
				if(arr[i] < arr[N]) {
					memo[N] = Math.max(memo[N], DP(i)+1);					
				}
			}
		}

		return memo[N];
	} // End of DP

} // End of Main class

Kotlin

import java.io.*
import java.util.*

private lateinit var memo : IntArray
private lateinit var arr : IntArray

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))

    var A = br.readLine().toInt()
    memo = IntArray(A)
    arr = IntArray(A)

    val st = StringTokenizer(br.readLine())
    for(i in 0 until A) arr[i] = st.nextToken().toInt()

    for(i in 0 until A) DP(i)

    var max = memo[0]
    for(i in 1 until A) max = Math.max(max, memo[i])

    print(max)
} // End of main

private fun DP(N : Int) : Int{

    if(memo[N] == 0) {
        memo[N] = 1

        for(i in N-1 downTo 0) {
            if(arr[i] < arr[N]) memo[N] = Math.max(memo[N], DP(i)+1)
        }
    }

    return memo[N]
} // End of DP