[백준] 17216번 : 가장 큰 감소 부분 수열 – JAVA [자바]

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

17216번: 가장 큰 감소 부분 수열

 

---

• 문제

 

---

• 문제 풀이

백준 17216번 가장 큰 감소 부분 수열은 DP, 그중에서도 특히 LIS를 이용해서 푸는 문제이다. LIS 이론을 공부하고 싶으면 밑에 있는 링크를 참고하면 되겠다.

 

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

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

이번 문제에서 주어진 예시를 한번 보겠다.

 

이 문제에서는 수열 A = {1, 100, 2, 50, 60, 8, 7, 3, 6, 5}가 주어졌고 감소하는 수열 중에 합이 가장 큰 부분 수열의 합을 구하면 되는 문제이다.

 

처음 dp 값은 첫 번째 Arr 값과 동일하다.

 

현재 값은 100이고 100보다 큰 이전 원소가 없으니 현재 dp 값은 100이다.

 

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

 

현재 값은 50이고 50보다 더 큰 이전 원소들 중 가장 큰 dp 값이 100 이므로 100+50 = 150을 현재 dp 값으로 저장한다.

 

현재 값은 60이고 60보다 더 큰 이전 원소들 중 가장 큰 dp 값이 100 이므로 100+60 = 160을 현재 dp 값으로 저장한다.

 

현재 값은 8이고 8보다 더 큰 이전 원소들 중 가장 큰 dp 값이 160 이므로 160+8 = 168을 현재 dp 값으로 저장한다.

 

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

 

현재 값은 3이고 3보다 더 큰 이전 원소들 중 가장 큰 dp 값이 175 이므로 175+3 = 178을 현재 dp 값으로 저장한다.

 

현재 값은 6이고 6보다 더 큰 이전 원소들 중 가장 큰 dp 값이 175 이므로 175+6 = 181을 현재 dp 값으로 저장한다.

 

현재 값은 5이고 5보다 더 큰 이전 원소들 중 가장 큰 dp 값이 181 이므로 181+5 = 186을 현재 dp 값으로 저장한다.

 

따라서 주어진 수열에서 {100, 60, 8, 7, 6, 5}가 가장 큰 감소하는 부분 수열이므로 최종 합은 186이다.

 

---

• 코드

 

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());
        int[] arr = new int[n+1];
        int[] dp = new int[n+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            dp[i] = arr[i];
        }
        int max = 0;
        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]+arr[i]);
            }
            max = Math.max(max, dp[i]);
        }
        System.out.print(max);
    }
}

 

---

• 후기

알고리즘 LIS에서 살짝만 응용해서 변형하면 쉽게 풀 수 있는 문제였던 거 같다.