11055 백준 C언어

 

이 문제는 11053과 유사한 문제이다.

나는 DP로 문제를 풀었다.

 

가장 큰 개요는

1. dp[i]배열에 현재 가장 큰 합을 넣어준다.

2. 그리고 input[i]가 input[j]보다 크다면 dp[i]와 dp[j] + input[i] 중 누가 더 큰지 비교한다.

3. max 값이랑 dp[i] 값이랑 비교한다.

 

이렇게 된다.

 

for (int j = 0; j < i; j++) {
	if (input[i] > input[j]) {
		dp[i] = my_max(dp[i], dp[j] + input[i]);
	}

}

 

i의 for문 안에 있는 j를 통해서 i까지 순환 시켜 가장 큰 합을 가진 dp를 구해준다.

각각의 dp에는 이미 가장 큰 합이 들어있기 때문에 이렇게 반복해도 된다.

#include<stdio.h>

int my_max(int a, int b) {

	return  a > b ? a : b;

}

int main() {

	//전에 input보다 현재 input이 더 크면 비교하기
	//이게 가장 중요한 알고리즘임

	int n;
	int input[1001]; // 숫자 입력 공간
	int dp[1001]; // 길이 저장되어 있는 곳
	int max = 0;

	dp[0] = 1;

	scanf_s("%d", &n);


	for (int i = 0; i < n; i++) {
		scanf_s("%d", &input[i]);
		dp[i] = input[i];

		for (int j = 0; j < i; j++) {
			if (input[i] > input[j]) {
				dp[i] = my_max(dp[i], dp[j] + input[i]);
			}
		
		}

		if (dp[i] > max)
			max = dp[i];
	}

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