본문 바로가기
Algorithm/Baekjoon

11055_가장 큰 증가 부분 수열

by 모너아링 2023. 1. 10.

▶실버2

풀이

기본적으로 dp[i] = arr[i]인 상태에서 arr[j](이전 값) < arr[i](현재 기준값)을 만족할 때, dp[j] + arr[i] 와 dp[i] 중 큰 값을 선택하여 dp[i]에 대입한다. 

위의 예제를 표로 나타내면

1 100 2 50 60 3 5 6 7 8
1 101 1 + 2 = 3 max(1, 3) + 50 = 53 max(1, 3, 53) + 60 = 113 max(1, 3) + 3 = 6 max(1, 3, 6) + 5 = 11 max(1, 3, 6, 11) + 6 = 17 max(1, 3, 6, 11, 17) + 7 = 24 max(1, 3, 6, 11, 17, 24) + 8 = 32

dp값 중 가장 큰 값이 답

코드

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int dp[1001];
int arr[1001];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n, ans = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		dp[i] = arr[i];
	}

	for (int i = 0; i < n; i++) {
		if (i == 0) {
			ans = dp[i];
		}
		for (int j = 0; j < i; j++) {
			//증가 수열 조건 만족
			if (arr[j] < arr[i]) {
				dp[i] = max(dp[j] + arr[i], dp[i]);
			}

			//증가 수열 조건 불만족
			else continue;

		}
		ans = max(ans, dp[i]);
	}
	cout << ans;
}

'Algorithm > Baekjoon' 카테고리의 다른 글

1699_제곱수의 합  (0) 2023.01.13
11660_구간 합 구하기 5  (0) 2023.01.11
11057_오르막수  (0) 2023.01.04
2003_수들의 합 2  (0) 2023.01.02
21921_블로그  (0) 2023.01.01