[백준 java] 11053 - 가장 긴 증가하는 부분 수열

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

---

최장 증가 부분 수열(Longest Increasing Subsequence) 알고리즘으로 풀 수 있는 문제이다.

어떤 수열이 주어지면 그 수열 내에서 (변형x) 오름차순으로 구성된 가장 긴 수열을 LIS 라고 한다.

 

이 알고리즘을 사용하기 전에는최소값 index를 구하여 해당 index부터 최장거리를 구하려고 했는데중복되는 최소값이 있으면 길이를 구하지 못해서 바로 틀렸다...

 

 

[BOJ] 백준 11053번 : 가장 긴 증가하는 부분 수열 (JAVA)

 

[Java]최장 증가 부분 수열(LIS, Longest Increasing Subsequence)

( 위 두 블로그에 그림과 같이 설명이 잘 되어있다 )

 

 

풀이방법

dp[i] 에는 해당 원소 i가 가질 수 있는 LIS 값으 ㄹ저장한다dp[ i ] 에는 현재값 i보다 작은 숫자 j (1 ~ i-1) 까지 dp를 비교하여 가장 큰 값 + 1을 dp[ i ] 값으로 가진다조건 두가지는 1.  arr[ j ] 값이 arr[ i ] 값보다 작아야한다.2. dp[ i ]는 dp [ j ] 보다 작거나 같아야한다.

 

만약 아래와 같은 예제가 있으면 (dp[1]부터 시작)

6
50 10 20 10 20 30

 

여기서 dp[1] 은dp[1] 는 첫번째 조건을 만족 못하니 본인길이1을 가지고 넘어간다.
{1}

 

dp[2] 를 구할때는 

dp[2] 는 arr[1] 보다 작으니 본인길이 1을 가지고 넘어간다.

{1,1}

 

dp[3] 은 arr[1] 은 넘어가고 arr[2] 보다 크고 dp[3]은 아직 0이니 두번째 조건도 만족하여  dp[2] + 1 = 2 가된다.{1,1,2}

 

...

 

dp[5]에서 arr[1]은 넘어가고

1. arr[5] 는 arr[2] 보다 크고 현재 dp[4]는 0이니 dp[2] +1 인 2를 가진다

2. arr[5] 는 arr[3] 보다 크고 현재 dp[4] 의 값은 2를 가지고 dp[3]은 2를 가지고 있으니

두번째 조건을 만족하여 2+1 = 3이된다.

3. arr[4] arr[5] 는 두번째 조건을 만족하지 못하여 넘어간다. 

(dp[4] = 1 , dp[5] = 2)

{1, 1, 2, 1, 2, 3}

 

따라서 해당 LIS의 최대값 3이 답이된다.

 

---

// https://www.acmicpc.net/problem/11053
// 가장 긴 증가하는 부분 수열

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

public class B11053 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] board  = new int[N+1];
        int[] dp = new int[N+1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            board[i] = Integer.parseInt(st.nextToken());
        }

        dp[1] = 1;
        int res = 1;
        // i = 현재값 j = 비교값
        for (int i = 2; i <= N; i++) {
            // 무조건 경로 수는 1이상이니 (본인 길이 1) 로 초기화
            dp[i] = 1;

            //현재 값과 이전의 값들을 비교하며 현재값의 경로 수를 구한다.
            for (int j = 1; j < i; j++) {

                // dp[i] <= dp[j] 는 중복되는 수를 더하지 않게하기위해 사용한다.
                // 만약 dp[4] 를 계산할때 10 20 10을 차례대로 다 더하게되면
                // dp[4] 는 4가되게 된다.
                if(board[i]>board[j] && dp[i] <= dp[j]){
                    dp[i] = dp[j] + 1;
                }
            }
            res = Math.max(res , dp[i]);
        }

        System.out.println(res);
        br.close();
    }
}

 

여러번 틀리고 풀이를 찾아서 LIS 알고리즘으로 풀었다. (아직 엄청 어렵다)

다른 LIS문제도 풀어봐야겠다...