[C++] 백준 11055번 - 가장 큰 증가 부분 수열

---

0. 문제

 

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

 

1. 아이디어

 

1) n번째 원소의 dp값 = n-1번까지의 원소들 중 자신보다 작은 값 중에 가장 큰 dp의 값 + 자신의 값

 

2. 소스코드

 

#include <iostream>
int main()
{
    int N, result = 0, arr[1000], dp[1000];
    std::cin >> N;
    for (int i = 0; i < N; i++)
        std::cin >> arr[i]; // arr에 수열의 값들 입력
 
    for (int i = 0; i < N; i++)
    {
        int max = 0;
        for (int j = 0; j < i; j++)
            if (arr[j] < arr[i]) // 자신보다 작은 값일 때
                if (dp[j] > max) max = dp[j];
        dp[i] = max + arr[i];
 
        if (dp[i] > result) result = dp[i];
    }
    std::cout << result;
}

 

3. 결과

 

 

4. 피드백

 

• 차곡차곡 쌓아간다는 DP의 느낌을 잘 기억하자!

---