[백준-11053번 자바/java] 가장 긴 증가하는 부분 수열 _디버깅의 눈물

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

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

 

 

 

 

 

가장 긴 증가하는 부분 수열 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

114730

45149

29770

37.340%

문제

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

예제 입력 1 복사

6
10 20 10 30 20 50

예제 출력 1 복사

4

 

 

---

 

 

체크 포인트

1. 다이나믹 프로그래밍(Dynamic Programming, 동적계획법) 이용

-큰 문제를 여러 가지 작은 문제로 나누어 해결해보는 DP를 이용했다.

-DP에는 1)Top-down(탑다운) 방식과 2)Bottom-up(바텀업)방식 두 가지가 대표적으로 존재한다.

 

1)Top-down(탑다운)은 가장 큰 문제를 방문한 후, 작은 문제를 찾아가는 방식이고, 재귀를 통해 구현한다.

2)Bottom-up(바텀업)은 가장 작은 문제를 방문 후, 큰 문제를 찾아가는 방식이고, 반복문(for문)을 통해 구현한다.

 

 여기서는 Bottom-up(바텀업) 방식으로 구현했다.

 

 

2. 가장 긴 증가하는 부분 수열의 길이 추론 과정

 

      A[0]  A[1]  A[2]  A[3]  A[4]  A[5]
        10   20    10    30    20    50 // 입력된 수열 A  
        
     dp[0] dp[1] dp[2] dp[3] dp[4] dp[5]
        1     2     1     3     2     4 // 가장 긴 증가하는 부분 수열의 길이 dp

 

1)입력된 첫번째 수열(10)에 대한 '가장 긴 증가하는 부분 수열의 길이'는 무조건 1이다.

 

2)두번째 수열에서부터 탐색 기준 수열보다 왼쪽에 위치한 수열 중, 기준 수열보다 작은 수열을 찾는다.

예시1)두번째 수열 20을 탐색 기준으로, 왼쪽에 위치한 수열(10) 중에서 기준 수열(20)보다 작은 수열은 (10)이다.

예시2)세번째 수열 10을 탐색 기준으로, 왼쪽에 위치한 수열(10 20) 중에서 기준 수열(10)보다 작은 수열은 없다.

예시3)네번째 수열 30을 탐색 기준으로, 왼쪽에 위치한 수열(10 20 10) 중에서 기준 수열(30)보다 작은 수열은 (10 20 10)이다.

...

 

3) 2)에서 찾은 수열 중에서, dp값이 가장 큰 수열을 찾고, 해당 값에 + 1을 하면 탐색 기준 수열의 '가장 긴 증가하는 부분 수열의 길이'가 된다.

예시1)기준 수열(20, A[1])보다 작은 수열은 (10)이고 dp값은 1이다. 따라서 기준 수열(20)의 dp값(dp[1])은 2가 된다.

예시2)기준 수열(10, A[2])보다 작은 수열은 없기 때문에, 기준 수열(10, A[2] 위치)의 dp값(dp[2])은 1이 된다.

예시3)기준 수열(30, A[3])보다 작은 수열은 (10 20 10)이고, 가장 큰 dp값(20, A[1])은 2이다. 따라서 기준 수열(30, A[3])의 dp값(A[3])은 3이 된다.

 ...

 

요약하자면,

 

특정 수열의 '가장 긴 증가하는 부분 수열의 길이'는, 

탐색 기준이 되는 수열보다 왼쪽에 있는 수열 중,

탐색 기준 수열보다 작은 수열이면서,

가장 긴 증가하는 부분 수열의 길이를 가지고 있는 것에 + 1을 한다. 

 

 

 

 

풀이

 

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

public  class Main {
	
	// 수열 A, 다이나믹 프로그래밍 배열 dp
	static int[] A,dp;
	
    public static void main(String[] args) throws IOException {
    	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	// 수열의 크기 N
    	int N = Integer.parseInt(st.nextToken());
    
    	// 수열 배열 초기화
    	A = new int[N];
    	// dp 배열 초기화 및 첫번째 값 초기화
    	dp = new int[N];
    	
    	st = new StringTokenizer(br.readLine(), " ");
    	
    	// 수열 배열에 수열 넣기
    	for(int i=0; i<N; i++){
    		A[i] = Integer.parseInt(st.nextToken());
    		// 모든 dp 기본값을 1로 초기화!
    		dp[i] = 1;
    		
    	}
    
    	// dp 탐색 실행
    	solution(N);
    	
    	// 최대값
    	int max = 0;
    	// 완성한 dp배열을 토대로, 가장 긴 증가하는 부분수열 찾기
    	for(int i=0; i<N; i++){
    		max = Math.max(max, dp[i]);
    	}
    	
    	System.out.println(max);
    	
    	
    	
    } // end of Main
    
    
    
    // bottom-up 방식 구현
    static void solution(int N) {
    	
    	// i를 기준으로,
    	for(int i=1; i<N; i++){
    		// i왼쪽에 해당하는 j들을 탐색
    		for(int j=i-1; j>=0; j--){
    			// 왼쪽의 숫자들 중에서 더 작은 숫자가 있다면,
    			if(A[i]>A[j]){
    				// 해당 숫자의 dp값(가장 긴 증가하는 부분 수열의 길이를 의미)이 더 크다면,
    				if(dp[i]<dp[j]+1){
    					dp[i] = dp[j]+1;
    				}
    			}
    		}
    		
    	} // end of for
    	
    } // end of solution
    
} // end of Main