[Java]백준 11053번 :: 가장 긴 증가하는 부분 수열

백준 온라인 저지 11053번 - 가장 긴 증가하는 부분 수열

Java 알고리즘 문제풀이

 

풀이

DP(다이나믹 프로그래밍) 문제입니다.

큰 문제를 작은 단위의 문제로 생각해서 푸는 알고리즘인데, 코딩테스트에 자주 출제되는 문항입니다.

 

문제를 해석해보면

• 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구한는 문제
• 수열 A = {10, 20, 10, 30, 20, 50}일때
• 가장 긴 증가하는 수열 {10, 20, 10, 30, 20, 50}

 

DP(다이나믹 프로그래밍)에서 중요한 것은 규칙을 찾거나, 어떤 일반식을 찾는 것이 키 포인트입니다.

 

먼저 A수열의 A[1], A[2]를 먼저 보면, A[1] < A[2]이므로 D[2] = D[1] + 1을 넣습니다.

이때 A[3]의 값은 A[2]보다 작고 A[1]과 값이 동일하므로 D의 값도 같다는 것을 알 수 있습니다.

세 번째로 A[4]를 진행한다. A[4]는 이전 index의 값 중에서 가장 큽니다. 이때 이전에 제일 큰 값을 +1한 값을 넣습니다.

똑같은 방식으로 진행합니다.

마지막으로 A[6]의 값이 가장 크고 D의 값도 제일 크게 나온다. 따라서 A[6]의 D값을 출력하면 됩니다.

 

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

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

		int n = Integer.parseInt(br.readLine());
		int arr[] = new int[n];
		int d[] = new int[n];

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

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

		d[0] = 1;

		for (int i = 1; i < n; i++) {
			d[i] = 1;
			for (int j = 0; j < i; j++) {
				if (arr[j] < arr[i] && d[i] <= d[j]) {
					d[i] = d[j] + 1;
				}
			}
		}

		int max = 0;
		for (int i : d) {
			max = Math.max(max, i);
		}

		System.out.println(max);
	}
}

 

이 문제와 유사한 증가하는 부분 수열을 구하는 문제가 있다.

풀어보지 않았다면 풀어보는 것을 추천합니다.

https://developer-mac.tistory.com/72