백준 11055번 가장 큰 증가 부분 수열

www.acmicpc.net/problem/11055

11055번: 가장 큰 증가 부분 수열

IDEA

LIS 알고리즘을 이용하는 문제다. 최근에 공부했어서 그런지 보자마자 보이네 헿

기존 LIS의 알고리즘의 문제점은 길이는 알 수 있어도 그 길이에 해당하는 원소들을 알 수 없다는 것이었다. 

11055번은 그걸 물어보는 문제같다. 어떤 원소들이 가장 긴 부분 수열을 이루는지! 

 

수열의 크기가 1000이라서 시간 복잡도 O($n^{2}$) 풀이를 사용했다. 

우선 자기 이전을 탐색하면 자신의 arr값보다 작은 arr 값을 가지는 값 중 가장 큰 dp값 + 1 을 넣어주었다. 

합에 대해서는 arr값이 자기보다 작은 인덱스의 dp값과 자신의 arr 값을 더해주었다. 

 

arr	1	100	2	50	60	3	5	6	7
dp[0]	1	2	2	3	4	3	4	5	6
dp[1]	1	101	3	53	113	6	11	17	24

예를 들어 인덱스 4에 대해서 arr[4] = 50이다. 

1. 인덱스 1~3 을 보며 자신보다 arr 값이 작으면서 그 중 가장 큰 arr를 가지는 인덱스를 찾는다. -> index = 3

2. 인덱스 3에 해당하는 dp[0] + 1을 dp값으로 가진다. -> dp[4][0] = dp[3][0] + 1

3. 인덱스 3에 해당하는 dp[1] + arr 이 새로운 증가부분 수열의 합이므로 dp[1]을 업데이트 시켜준다. 

-> dp[4][1] = dp[3][1] + arr[4]

 

그리고 dp[n]이 가장 큰 합이 아니기때문에 매번 nmax를 통해 가장 큰 합을 업데이트해준다. 

 

CODE

#include <iostream>

using namespace std;

int arr[1001] = {0};
int dp[1001][2] = {0};

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n , nmax = 0;
	cin >> n;
	for (int i = 1; i <= n; i++)  cin >> arr[i];
	for (int i = 1; i <= n; i++) {
		//증가하는 부분 수열 구하기 
		for (int j = 0; j < i; j++) {
			if (arr[i] > arr[j]){
                dp[i][0] = max(dp[i][0], dp[j][0] + 1);
                dp[i][1] = max(dp[i][1], dp[j][1] + arr[i]);
                nmax = max(nmax, dp[i][1]);
            } 
		}
	}
	cout << nmax;
}

 

남의 코드

- 시간은 똑같은데 메모리가 절반이라서 보았더니, 1차원 dp를 사용하셔서 그런 거 같다. 

  내 코드 속의 연속수열의 길이를 따지는 과정은 사실 문제풀이에 필요하지는 않다.

  이 분의 코드가 딱 핵심만 간결하게 볼 수 있는 코드같다.

  현재 인덱스가 i라면 arr[i]보다 작으면서, dp + arr를 했을 때, 기존 dp 값보다 증가한다면 업데이트해준다.  

#include <stdio.h>
using namespace std;

int A[1001];
int dp[1001];

int main()
{
    int n,i,j;
    int m=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&A[i]);
    }
    for(i=1;i<=n;i++)
    {
        dp[i]=A[i];
        for(j=1;j<i;j++)
        {
            if(A[i]>A[j] && dp[j]+A[i]>dp[i])
            {
                dp[i]=dp[j]+A[i];
            }
        }
        if(m<dp[i])
        {
            m=dp[i];
        }
    }


    printf("%d",m);
    return 0;
}