DP - 11053. 가장 긴 증가하는 부분 수열

문제

www.acmicpc.net/problem/11053

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

 

잠깐만

오랜만에 이중포문을 사용합니다. 수행 및 종료타이밍을 확인하세요

 

코드

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int inputNum = Integer.parseInt(st.nextToken());
		
		int maxLength = 0;
		int[] values = new int[inputNum+1];
		int[] results = new int[inputNum+1];
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= inputNum; i++) {
			values[i] = Integer.parseInt(st.nextToken());
			
			for (int j = i-1; j > 0; j--) {
				if (values[j] < values[i] && results[i] < results[j]) {
					results[i] = results[j];
				}
			}
			results[i] += 1;
			maxLength = Math.max(maxLength, results[i]);
		}
		System.out.print(maxLength);
	}
}

 

설명

의외로 쉬운것 같은데 어렵고 어려운것 같은데 쉬운 문제입니다.

이중 포문을 통해서, value가 자신보다 작은 녀석들 중에서, max result(연속 개수)값을 가져오는 로직입니다

 

 

회고

이중 포문에 대한 종료 시점이라고 볼수 있겠네요