BAEKJOON / 백준 - JAVA 11053번 가장 긴 증가하는 부분 수열

2024.05.10기준 - 실버2

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 다이나믹프로그래밍을 이용하여 풀 수 있는 문제입니다.

 

수열 A를 저장하는 arr배열과 해당 배열(arr[i])에 해당하는 최대 수열 길이를 저장하는 dp배열을 선언하여 문제에 접근했습니다.

 

초기에 dp값은 어떤 수가 나와도 자기 자신을 포함하고 있기 때문에 수열의 초기 길이는 1로 잡아줍니다.

 

현재 받은 값(i)와 현재 보다 작은 값(j)를 비교해 i가 j보다 클 경우를 구합니다.

i가 j보다 크다면 그 중 가장 수열의 길이가 긴 dp값을 가져와 +1을 해주면 최대 수열의 길이가 구해지는 코드입니다.

 

 

코드

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine()); // 수열 길이
		StringTokenizer st = new StringTokenizer(br.readLine()); // 수열
		
		int[] arr = new int[n]; // 수열을 저장할 배열
		int[] dp = new int[n]; // DP 테이블
		
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
        // 가장 긴 증가하는 부분 수열 길이 구하기
		for (int i = 0; i < n; i++) {
        	// 모든 원소는 적어도 자기 자신만으로 증가하는 부분 수열을 형성하기 때문에 초기값은 1로 설정
			dp[i] = 1;
			
            // 현재 위치(i) 이전의 원소들과 비교하여 현재 위치에서의 최대 부분 수열 길이 구하기
			for (int j = 0; j < i; j++) {
				if (arr[j] < arr[i] && dp[i] < dp[j] + 1) {
					dp[i] = dp[j] + 1; // 현재 위치에서의 최대 부분 수열 길이 갱신
				}
			}
		}
		
        // 최대 부분 수열 길이 찾기
		int max = -1;
		for (int num : dp) {
			max = Math.max(max, num);
		}
		
		bw.write(Integer.toString(max));
		bw.flush();
		bw.close();
		br.close();
	}
}