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

풀이방법

 

2022.01.26

입력값으로 n개의 정수 배열이 주어진다.

이 정수 배열을 nums라 부르자.

 

길이가 n인 정수 배열 dp를 만든다.

dp[i] 는 nums[i]를 마지막 순서로 갖는 가장 긴 증가하는 배열의 길이이다.

 

예를 들어, 아래의 표를 보자.

nums	10	20	10	30	20	50
dp	1	2	1	3	2	4

nums[0]의 값은 10이다.

10으로 끝나는 가장 긴 증가하는 배열은 {10}이다.

{10}의 길이는 1이다.

따라서 dp[0]은 1이다.

 

nums[3]의 값은 30이다.

30으로 끝나는 가장 긴 증가하는 배열은 {10, 20, 30}이다.

{10, 20, 30}의 길이는 3이다.

따라서 dp[3]은 3이다.

 

이를 코드로 구현한 뒤에 dp 배열의 요소 중 가장 큰 것을 화면에 출력하면 문제가 해결된다.

 

 

 

dp[i]를 구하는 방법은 다음과 같다.

 

nums[0] ~ nums[i-1]을 탐색하며 nums[i]보다 값이 작은 것들을 찾는다.

이렇게 찾은 값들 중 가장 큰 것의 dp값에 1을 더하면

dp[i]값과 같다.

 

예를 들어 위 표에서 30과 50의 경우를 보자.

{10, 20, 30}이 있기 때문에 dp[3]은 3이다. 이를 이용해 dp[5]를 구할 수 있다.

 

30<50이다. 그리고 50보다 앞에 있는 수 중 30이 가장 크다.

 

그럼 50으로 끝나는 가장 긴 증가수열은

{10, 20, 30}

의 마지막에 50을 덧붙인

{10, 20, 30, 50}

이다.

 

이러한 성질을 이용하여,

dp[3]+1 = dp[5]임을 알 수 있다.

 

※nums의 값이 가장 크면 dp의 값도 반드시 가장 크기 때문에,

나는 가장 큰 nums값이 아니라 가장 큰 dp값을 찾아 거기에 1을 더하였다.

 

코드

Java(2022.01.26)

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		//n 읽어오기
		int n = Integer.parseInt(br.readLine());
		
		//정수 배열 읽어오기
		String[] input = br.readLine().split(" ");
		int[] nums = new int[n];
		for(int i = 0; i<n; i++) {
			nums[i] = Integer.parseInt(input[i]);
		}
		
		int[] dp = new int[n];
		
		dp[0] = 1;
		
		for(int i= 1; i<n; i++) {
			dp[i] = 1;	//가능한 가장 작은 dp값인 1로 초기화
			for(int j = 0; j<i; j++) {
            	//자신보다 앞순서에서,
                //(숫자값)이 자신보다 작은 동시에 (dp값+1)이 자신보다 큰 경우를 발견하면,
                //해당 (dp값+1)을 취한다.
				if(nums[j]<nums[i] && dp[i]<dp[j]+1) {	
					dp[i] = dp[j]+1;
				}
			}
		}
		
		//dp 중 가장 큰 값을 구하여 출력
		Arrays.sort(dp);
		System.out.print(dp[n-1]);

	}

}