[백준] 11055_가장 큰 증가 부분 수열 (C++)

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

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

 

 

[규칙]

1. 증가 부분 수열
2. 합이 가장 큰 것

 

[실패 원인]

1. 알고리즘은 간단하였는데, 비교하는 부분에서 합이 큰 값이랑 비교를 안 하고 자신과 작은 값의 수열과 비교해서 틀렸다.

 

[풀이 설명]

• 증가하면서 합이 가장 큰 것을 선택하면 된다. 
• 나는 배열을 따로 만들어서, 각자 증가하는 부분에 있어서 합을 각 행마다 저장을 했다. 
• 이게 무슨 말이라면, 
•  

  

자신보다 작은 값의 최댓값과 자신을 더하면 된다고 생각했다. 

ex) 50은 자신보다 작은 값이 1과 2가 있다. 

그치만 2는 1을 이미 더한 값이기 때문에 2의 값만 더해주면 된다. (연한 주황색 화살표 참조)

 

[소스코드]

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

int main() {
	int N, output_max_num = 0;

	cin >> N;
	vector<int> input_A(N + 1), add_array(N+1,0);
	
	for (int i = 0; i < N; i++)
		cin >> input_A[i];

	for (int i = 0, max_add_num; i < N; i++) {
		max_add_num = 0;
		for (int j = 0; j < i; j++) {
			if (input_A[i] > input_A[j])
				max_add_num = max(max_add_num, add_array[j]);
		}
		add_array[i] = input_A[i] + max_add_num;
		output_max_num = max(output_max_num, add_array[i]);
	}
	cout << output_max_num;
	
	return 0;
}