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

1. 풀이 힌트 

 - 어떤 인덱스의 크기를 기준으로 첫 번째 인덱스 부터 해당 인덱스 앞까지 값을 비교하면서, 부분 수열의 크기를 카운트해준다.

2. 풀이 과정

1) 6개의 숫자 10, 20, 10, 30, 20, 50를 저장하는 배열(arr)을 선언하고, 해당 배열안의 숫자들의 크기를 비교하여 부분 수열의 크기를 카운트한 수를 저장하는 배열(dp)을 선언한다.

arr (저장된 값)	10	20	10	30	20	50
dp (큰 순서)	0	0	0	0	0	0

수열의 크기가 6이므로 총 6번의 비교 작업을 수행한다.

 

2) 첫번째 비교 작업 (i = 1)일 때는 첫번째 수가 가장 큰 수이므로 해당 dp값으로 +1을 추가한다.

arr (저장된 값)	10	20	10	30	20	50
dp (큰 순서)	1	0	0	0	0	0

3) 2번째 비교 작업 (i = 2)일 때는 우선 2번째 저장값의 dp값을 +1 한 뒤, 2번째 저장값과 그전 1번째 저장값을 비교하여, 만약 2번째 저장값이 더 크고(10 < 20), dp값이 같거나 작으면 (1 = 1) 순서를 +1 해준다(최종 dp = 2).

arr (저장된 값)	10	20	10	30	20	50
dp (큰 순서)	1	2	0	0	0	0

4) 3번째 비교 작업 (i = 3)시에도 우선 dp값을 1로 설정한 뒤 2번째 값과 1번째 값을 순차적으로 비교하여, 3)에서 시행했던 대로 i번째의 값이 i - 1번째 값보다 크고, dp값은 적거나 같다면 dp값을 +1 한다.

arr (저장된 값)	10	20	10	30	20	50
dp (큰 순서)	1	2	1	0	0	0

5) 위와 같이 6번의 비교 작업을 거치면 밑과 같은 결과가 나온다.

i = 4

arr (저장된 값)	10	20	10	30	20	50
dp (큰 순서)	1	2	1	3	0	0

i = 5

arr (저장된 값)	10	20	10	30	20	50
dp (큰 순서)	1	2	1	3	2	0

i = 6

arr (저장된 값)	10	20	10	30	20	50
dp (큰 순서)	1	2	1	3	2	4

6) 가장 긴 증가하는 부분 수열은 dp값 중에서 가장 큰 값인 4가 된다.

3. 코드 구현

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

// 11053 가장 긴 증가하는 부분 수열
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());
        
        int[] arr = new int[1001]; // arr : 수열의 값 저장
        int[] dp = new int[1001]; // dp : 부분 수열의 크기 저장
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        for (int i = 1; i <= n; i++) { // 1) 수열의 값 저장하기.
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        for (int i = 1; i <= n; i++) { // 2) 비교 작업 수행하기
            dp[i] = 1; // 부분 수열의 기본 크기는 1
            for (int j = 1; j < i; j++) { // 3) 현재 인덱스(i)부터 1 ~ i - 1까지 순차적으로 비교
                if (arr[j] < arr[i] && dp[i] <= dp[j]) { // 4) 조건에 맞으면 부분 수열 크기 증가
                    dp[i]++;
                }
            }
        }
        
        int max = 0;
        for (int i = 1; i <= n; i++) { // 5) 부분수열의 최대 값 출력
            max = Math.max(max, dp[i]);
            System.out.println(dp[i]);
        }
        
        System.out.println(max);

    }

}

 

문제링크

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