문제

BOJ 11053: 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053

풀이

조건

• 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성한다.

풀이 순서

• i번째 수열의 값이 j번째 수열의 값보다 크다면 증가한다는 뜻이다.
• dp[i]의 값을 구하고 바로 최댓값도 구한다.

코드

Java

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

public class Main {

	static int N; // 수열 크기
	static int[] arr; // 수열

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		arr = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		// 1000 크기의 DP 배열을 1로 초기화 -> 길이는 최소 1이기 때문
		int[] dp = new int[1000];
		for (int i=0; i<1000; i++) {
			dp[i] = 1;
		}
		
		int answer = 1;
		for (int i=1; i<N; i++) {
			for (int j = 0; j < i; j++) {
				// i번째 수열의 값이 j번째 수열의 값보다 크다면 -> 증가한다는 뜻
				if (arr[i] > arr[j]) {
					// j번째 DP 값 + 1 과 i번째 DP 값 중 더 큰 값으로 DP i번째 값 갱신
					dp[i] = Math.max(dp[j] + 1, dp[i]);
				}
				// 최대 길이 찾기
				if (dp[i] > answer) {
					answer = dp[i];
				}
			}
		}
		
		System.out.println(answer);
	}
	
}

정리

• 예외 케이스 -> n이 1일 때를 처리 안해줘서 틀렸었다.