백준 | 11053번. 가장 긴 증가하는 부분 수열 - DP 문풀

⬛ 백준 11053번. 가장 긴 증가하는 부분 수열 - DP 문풀

https://www.acmicpc.net/problem/11053

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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

---

💚 문제 접근 방식

• dy[N] 정의 : 0~N까지 N을 포함하여 만들 수 있는 가장 길게 증가하는 수열의 길이
• 만약 현재 arr[N]보다 작은 값이 앞쪽에 위치해 있다면 그 값들 중 가장 max를 갖는 dy[j]를 활용해서 현재의 dy[N] = dy[j] + 1 처리를 하도록 했다.

풀이 부연 설명

극단적으로 N이 1 이 들어올수도 있다. 이런 부분은 늘 주의하자.

---

💚 제출 코드

import java.util.Scanner;

/**
 * 11053번. 가장 긴 증가하는 부분 수열 - DP 문풀
 * @author MYLG
 *
 */
public class Main {
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		int N = kb.nextInt();
		int[] arr = new int[N+1];
		int[] dy = new int[N+1];
		
		for(int i=1; i<=N; i++) {
			arr[i] = kb.nextInt();
		}
		
		//dy[N] 정의 : 0~N까지 현재값을 포함하여 만들 수 있는 가장 긴 증가 길이 
		
		dy[1] = 1; //자기 자신에 대한 길이 1
		int answer = 0;
		
		if(N >= 2) {
			if(arr[2] > arr[1]) dy[2] = dy[1] + 1;
			else dy[2] = 1;
		}
		
		for(int i=3; i<=N; i++) {
			int max = 0;
			for(int j=0; j<i; j++) { //앞쪽에서 돌면서 
				if(arr[i] > arr[j]) { //현재보다 작은 값 가지면서 
					max = Math.max(max, dy[j]); //dy[j] 값 중에선 max를 갖는 값으로 갱신 
				}
			}
			dy[i] = max + 1;
		}
		
		for(int i=1; i<= N; i++ ) {
			answer = Math.max(answer, dy[i]);
		}
		System.out.println(answer);
	}
}