백준-11053번/가장 긴 증가하는 부분 수열 (java)

 

 

 

우선 정수형 배열을 받아줄 배열 arr와 증가하는 수열의 길이를 나타낼 dp를 만들었다.

 

8

1 8 9 9 9 2 3 4

이러한 입력을 받았을때를 생각해보면 arr[5]에서 dp[5]를 arr[4]랑만 비교해서 바로 dp[5]를 1로 만들면 안되고 arr[0]과 연결되는 수열을 만들 수 있으므로 dp[5]는 2가 된다.

따라서 dp를 결정할때 앞의 수와 모두 비교를 해 줘야 한다.

 

i ==> 현재 비교하는 배열 요소

j ==> i의 전까지의 배열 비교

 

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

만약 arr[i]가 arr[j]보다 큰데 dp[i]보다 dp[j]가 작거나 같으면 증가되는 수열이다.

따라서 dp[i]를 dp[j]에서 1 증가시킨 값으로 넣어준다.

 

 

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n=scanner.nextInt();
		int bigc=0;
		int[] arr=new int[n];
		int[] dp=new int[n];
		
		for(int i=0; i<n; i++) {
			arr[i]=scanner.nextInt();
		}
		for(int i=0; i<n; i++) {
				dp[i]=1;
			
			for(int j=0; j<i; j++) {
				if(arr[i]>arr[j]&&dp[i]<=dp[j]) {
					dp[i]=dp[j]+1;
				}
			}
		}
		int big=0;
		for(int i=0; i<n; i++) {
			if(dp[i]>big) {
				big=dp[i];
			}
		}
		System.out.println(big);
	}
}