(BOJ) 11055 가장 큰 증가 부분 수열

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

문제 풀이:

ex)

10
1 100 2 50 60 3 5 6 7 8

배열 arr[ ]에 순서대로 1 100 2 50 60 3 5 6 7 8 넣음

또 다른 배열 dp[]에 arr[]와 똑같이 초기화 함

그 후 해당 위치를 pos라고 할 때

pos가 0일 때(인덱스 0) : dp[0]=1

pos가 1일 때 : dp[1]=dp[0]+dp[1]=101

pos가 2일 때 : dp[2]=dp[0]+dp[2]=3

.

.

.

즉 현재 pos 이전 인덱스들을 확인해서

arr값이 본인보다 작으면서 dp값이 현재 자신보다 큰 것들을 찾아 더함

소스 코드:

#include <iostream> #include <queue> #include <vector> #include <string> #include <string.h> #include <tuple> #include <algorithm> #define inf 987654321 using namespace std; int n, arr[1001],dp[1001],res; int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n; for (int i = 0; i < n; i++) { cin >> arr[i]; dp[i] = arr[i]; for (int j = 0; j < i; j++) { if (arr[j] < arr[i] && dp[i] < dp[j] + arr[i]) { dp[i] = dp[j] + arr[i]; } } res = max(res, dp[i]); } cout << res << '\n'; return 0; }