[BAEKJOON]11055 가장 큰 증가하는 부분 수열

문제 요약

• 알고리즘 분류: dp, LIS
• 난이도:  Silver2
• 문제내용:
  • 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.
  • 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

• 사이트: https://www.acmicpc.net/problem/11055

문제풀이

 이번 문제에는 모든 경우의 수를 구해서 풀기가 힘들다. 모든 경우의 수를 구하 O(N^N)개 이상으로 나올수 있다. 그래서 이번 문제는 LIS 개념을 적용해서 풀어야 한다. LIS에 대한 개념은 아래 글에서 확인 해보면된다.

https://jih3508.tistory.com/46

[알고리즘 이론] LIS(Longest Increasing Subsequence) 최장 증가 부분 수열

이번 문제는 LIS 기초 개념만 알면 푸는것인데 다만 증가하는 수열의 개수를 구하는것이 아니라 증가하는 수열들 중에서 가장 큰 합을 구하는것이다. 그래서 점화식을 아래와 같이 변경하면 되고 나머지는 코드 보면 이해가 될것이다.

• 기존: 뒤에것 보다 클 경우 뒤에 개수 + 1과 현재 개수 비교해서 큰 값을 지정
• 변경점: 뒤에것 보다 클 경우 뒤에 누적 합 + 현재 지정된 수와 현제 누적된 값중 큰 값을 지정

Code

 LIS중 데이터 양이 최대 1000개라서 DP로 풀수 있어서 간단하게 DP로 했다.

Python

N = int(input())
A = list(map(int, input().split()))
dp = [num for num in A]

for i in range(1, N):
    for j in range(i):
        if(A[i] > A[j]):
            # 이전 값들과 비교해서 큰 값이면 이전 저장 되는 것과 수열 개수 비교
            dp[i] = max(dp[i], dp[j] + A[i])

# dp 배열중 가장 길게 저장 된 결과 값을 가져온다.
print(max(dp))

Java

import java.util.*;
import java.io.*;

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[] dp = new int[N];
		int[] nums = new int[N];
		for (int i = 0; i < N; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
			dp[i] = nums[i];
		}

		for (int i = 1; i < N; i++) {
			for (int j = 0; j < i; j++) {
				// 이전 값들과 비교해서 큰 값이면 이전 저장 되는 것과 수열 개수 비교
				if(nums[i] > nums[j]){
					dp[i] = Math.max(dp[i], nums[i] + dp[j]);
				}
			}
		}

		System.out.println(Arrays.stream(dp).max().getAsInt());

	}
}