[Baekjoon/백준] 1912번: 연속합(C/C++)

단계별로 풀어보기 15단계(동적 계획법 1) 15번 문제

https://www.acmicpc.net/step/16

동적 계획법 1 단계

---

백준 1912번: 연속합

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

1912번: 연속합

---

문제 설명

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

---

입력과 출력

입력: 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력: 첫째 줄에 답을 출력한다.

---

접근 방법

이번 문제는 정수 n을 입력받고 n개의 수열을 입력받아서, 연속하는 몇개의 수를 선택해 구할 수 있는 합 중 가장 큰 합을 구해 출력하는 문제다. 예제 3번처럼 수를 하나만 선택하는 것도 가능하다.

우선 수열에는 음수도 입력될 수 있다. 그래서 최대 부분합을 구하는 이 문제에서 현재 추가하려는 값에 이전까지의 합을 더하는데 있어서 이전까지의 합 또는 이전 값이 음수라면, 더하는 의미가 없다. 고로 현재까지의 합은 이전까지의 합이 0보다 작다면, 그냥 0으로 만들어서 현재 추가 값만 저장되도록 만들어야 한다. 이렇게 저장된 이전까지의 합과 최대 부분 합 값을 또 비교해서 더 큰 값을 최대 부분 합으로 저장하도록 만든다면 문제를 해결할 수있다.

설명으로 쓰니 조금 이상한 것 같지만, 아래 코드를 보면 이해할 수 있을 것이라고 생각한다.

---

코드

#include <stdio.h>
#define MIN -1001

int findMax(int x, int y) {
	return x > y ? x : y;
}

int main(int argc, char *argv[]) {
	int n, sequence, max = MIN, sum = 0;
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf("%d", &sequence);
		sum = findMax(sum, 0) + sequence;
		max = findMax(sum, max);
	}

	printf("%d\n", max);

	return 0;
}

---

결과

백준 제출 결과