c언어 1912번 연속합 (백준)

#include <stdio.h>

int main(void)
{
	int n = 0;
	scanf("%d", &n); //몇 개?
	
	int dp[n]; //dp
	int max = 0; //최댓값
	
	for(int i = 0; i<n; i++)
	{
		static int tmp = 0;
		scanf("%d", &tmp);
		dp[i] = tmp;
		if(i == 0) max = dp[i]; //처음에 입력 받는 값을 max로
		else { //i 가 1 이상
			if(dp[i] < tmp + dp[i-1]) //입력 받은 수가 바로 전 것의 최댓값에 더한 것보다 작을 경우
				dp[i] = tmp + dp[i-1]; //dp = 입력 받은 수 + 바로 전 것의 최댓값
                
                
                
                
			if(max < dp[i]) max = dp[i]; //max보다 dp가 더 크면 교체
		}
	}
	printf("%d", max);
	
	return 0;
}

 

• 풀이

 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구해야 한다.

이를 위해선, 차근차근히 하면 된다!

 

ex)

10
10 -4 3 1 5 6 -35 12 21 -1

(1)

input : 10

dp[0] = 10

max = 10;

 

(2)

input : -4

처음에 dp[1]은 -4이나, 이전의 수에서 구할 수 있는 가장 큰 합은 10 이므로, dp[1] = -4 + dp[0], dp[1] = 6이다.

max = 10;

 

(3)

input : 3

처음에 dp[2]은 3이나, 이전의 수에서 구할 수 있는 가장 큰 합은 6이므로, dp[2] =  6 + 3, dp[2] = 9이다.

max = 9;

 

...

 

(9)

input : 21

처음에 dp[8]은 21이나, 이전의 수에서 구할 수 있는 가장 큰 합은 12이므로, dp[8] = 12 + 21, dp[8] = 33이다.

max 은 21이였으나 (max = dp[5] = 21) dp[8]이 더 크기 때문에,

max = 33;

...

 

output : 33

 

 

 

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

1912번: 연속합