백준 1912 연속합

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

 

 

서론

https://hydroponicglass.tistory.com/4

위와 같은 아이디어는 배열이 너무 커서 선언이 되질 않았다.

그래서 이중 for문으로 풀어봤으나 시간초과

결과적으로 DP를 이용한 단일 for문으로 풀어야 하는 문제였다.

 

 

풀이

예제

 

1	2	3	4	5	6	7	8	9	10
10	-4	3	1	5	6	-35	12	21	-1

 

sum[6]은 1번부터 6번까지의 합인 21이 저장되어있음

sum[6]은 sum[5]보다 큰 수이므로 결과값은 16에서 21로 갱신

sum[7]은 -14로 음수이므로 sum[7]은 0으로 갱신 (음수를 더해줄 시 최대값과 멀어짐)

sum[8]은 sum[7]이 0이므로 부분합을 0부터 다시 시작함

 

 

반례

Q. 라인24  if (i == 1) result = input;

A. 입력이 음수값만 있을때 초기 선언된 result가 0이므로 음수로 갱신되지 않는것을 해결

 

Q. 라인31 result = max(sum[i], result);

A. sum[6]이 음수이고 sum[7]도 음수인 경우를 위해 결과값과의 최대값 비교 후 갱신 

 

 

전체코드

//C++

#pragma warning (disable : 4996)

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

#define MAX_SIZE 100001

int sum[MAX_SIZE];

int result;

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int input;
		scanf("%d", &input);
		// -10의 반례
		if (i == 1) result = input;
		sum[i] = sum[i - 1] + input;
		if (sum[i] > 0) {
			result = max(sum[i], result);
		}
		else {
			// -3 -2의 반례
			result = max(sum[i], result);
			sum[i] = 0;
		}
	}
	printf("%d", result);
}

 

 

실패한 풀이

실패사유 : 시간초과

#pragma warning (disable : 4996)

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

#define MAX_SIZE 100001

int sum[MAX_SIZE];
int dp[MAX_SIZE];
int result;

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j++) {
			if (i == 1) {
				int input;
				scanf("%d", &input);
				sum[j] = sum[j - 1] + input;
				result = max(result, sum[j]);
			}
			else {
				result = max(result, sum[j] - sum[i - 1]);
			}
		}
	}
	printf("%d", result);
}