[Java+Python]11053번, 가장 긴 증가하는 부분 수열

문제

 

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

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

A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

입력

 

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

 

출력

 

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

풀이

 

티어는 하나 낮지만 왜인지 포도주 마시기 문제보다 어려웠던 문제이다.

 

메모이제이션을 위한 배열을 갱신하는 부분이 특히 어려웠는데,

 

2차원이 아니라 1차원으로 선언한 뒤 그때그때 바꾸는 방식은

 

깔끔하고 좋긴 하지만 내가 완전히 받아들이기엔 시간이 아직 조금 더 필요하다는 생각.

 

그 외에는 기본적인 동적계획법 문제와 푸는 법이 크게 다르지 않다.

 

먼저 자바.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Prob11053 {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		int[] memo = new int[n];
		Arrays.fill(memo, 1);
		int result = 1;

		StringTokenizer st = new StringTokenizer(br.readLine());

		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < i; j++) {
				if (arr[j] < arr[i] && memo[i] < memo[j] + 1) {
					memo[i] = memo[j] + 1;
					result = Math.max(result, memo[i]);
				}
			}
		}

		System.out.println(result);
	}
}

그리고 파이선 코드이다.

import sys

n = int(sys.stdin.readline().rstrip())
lst = list(map(int, sys.stdin.readline().rstrip().split()))
memo = [1 for _ in range(n)]
result = 1

for i in range(n):
    for j in range(i):
        if lst[j] < lst[i] and memo[i] < memo[j] + 1:
            memo[i] = memo[j] + 1
            result = max(result, memo[i])

print(result)