[백준] 11053. 가장 긴 증가하는 부분 수열

문제

 

풀이

처음으로 접근했던 방법은 index를 통해 메모이제이션을 수행하려고 했다. 하지만 같은 수가 존재할 경우 갱신하는 과정에서 일관된 규칙을 찾을 수 없었고 이를 커버하기 위해 index가 아닌 실제 값을 통해 메모이제이션을 수행했다.

앞에서부터 순서대로 해당 값 A를 찾고 1 ~ A-1까지의 최대 길이 + 1로 증가하는 부분 수열의 최대 길이를 저장했다.

import java.util.Scanner;

public class Solution11053 {
	static Scanner sc = new Scanner(System.in);
	static int[] cache = new int[1001];

	public static void main(String[] args) {
		int N = sc.nextInt();
		int[] input = new int[N];

		for (int i = 0; i < input.length; i++) {
			input[i] = sc.nextInt();
		}

		for (int i = 0; i < input.length; i++) {
			int current = input[i];
			int maxCnt = 0;
			for (int j = current - 1; j > 0; j--) {
				if (cache[j] == 0)
					continue;
				maxCnt = (maxCnt < cache[j]) ? cache[j] : maxCnt;
			}
			cache[current] = maxCnt + 1;
		}

		int maxCnt = 0;
		for (int i = 1; i < 1001; i++) {
			if (maxCnt < cache[i]) {
				maxCnt = cache[i];
			}
		}

		System.out.println(maxCnt);
	}
}