[백준] 7861번 : Longest Ordered Subsequence – JAVA [자바]

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

7861번: Longest Ordered Subsequence

 

---

• 문제

---

• 문제 풀이

백준 7861번 Longest Ordered Subsequence는 백준 11053번 가장 긴 증가하는 부분 수열이랑 똑같은 문제이고 LIS를 이용해서 푸는 문제이다.

 

LIS 이론을 공부하고 싶으면 밑에 있는 링크를 참고하면 되겠다.

 

※참고※ : https://propercoding.tistory.com/41

[알고리즘] LIS (최장 증가 부분 수열)

 

이번 문제도 주어진 예제를 한번 보겠다.

 

이 문제에서는 수열 arr = (1, 7, 3, 5, 9, 4, 8)이 주어졌도 LIS의 길이를 출력해주면 된다.

처음 dp 값은 1로 시작한다.

 

현재 값이 7이고 7보다 작은 이전 원소들 중 가장 큰 dp값이 1이므로 1 + 1 = 2를 현재 dp값으로 저장한다.

 

현재 값이 3이고 3보다 작은 이전 원소들 중 가장 큰 dp값이 1이므로 1 + 1 = 2를 현재 dp값으로 저장한다.

 

현재 값이 5이고 5보다 작은 이전 원소들 중 가장 큰 dp값이 2이므로 2 + 1 = 3을 현재 dp값으로 저장한다.

 

현재 값이 9이고 9보다 작은 이전 원소들 중 가장 큰 dp값이 3이므로 3 + 1 = 4를 현재 dp값으로 저장한다.

 

현재 값이 4이고 4보다 작은 이전 원소들 중 가장 큰 dp값이 2이므로 2 + 1 = 3을 현재 dp값으로 저장한다.

 

현재 값이 8이고 8보다 작은 이전 원소들 중 가장 큰 dp값이 3이므로 3 + 1 = 4를 현재 dp값으로 저장한다.

 

따라서 LIS의 길이는 4이다.

 

---

• 코드

 

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n+1];
        int[] dp = new int[n+1];
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            dp[i] = 1;
        }
        int max = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                if (arr[i] > arr[j]) dp[i] = Math.max(dp[i],dp[j]+1);
            }
            max = Math.max(max, dp[i]);
        }
        System.out.print(max);
    }
}

 

---

• 후기

이번 문제도 LIS 문제여서 쉽게 풀 수 있었다.