백준 1912 연속합

#재채점으로 오답이 나신분들이 검색으로 이 글을 많이 들어오시는 것 같다.

이 해법은 테스트케이스가 추가된(17년 12월쯤..) 후에도 정답이니, 걱정마시고 참고하시면 될거 같다.

#이렇게 접근 했다.

1. 숫자를 0번부터 차근차근 더해가면서 memo배열에 현재까지의 합을 기록한다.

2. 더해가다가 memo에 음수를 기록하게 되면 그 다음 부터는 합을 0으로 초기화하고 다시 더한다

3. 1~2번 작업을 끝까지 마친 후 memo의 값중 최대값을 출력한다.

이 알고리즘을 요약하면, '합이 음수가 되는 지점이 생기면 그 이전의 숫자는 모두 신경 쓰지 않는다' 이다.

최적화를 조금 해보면

memo를 사용 하지 않고 그냥 최대값만 저장하는 변수 하나만 쓰면 되고,

숫자를 더할때도 입력받으면서 바로바로 더하면 된다.

그래서 처음 만든 코드가 이것.

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

int main() {
	int N;
	cin >> N;
	int sum = 0, result = 0;
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		if (sum + num > 0) {
			sum += num;
			result = max(result, sum);
		}
		else {
			sum = 0;
		}
	}
	cout << result << endl;
	return 0;
}

근데 오답이 났다.

별 생각 할 거리도 없이, 결과가 음수일 경우에 오답이겠구나 싶었다. 왜냐면 result를 0으로 잡고 시작했으니까.

결과가 음수일 경우란, 모든 입력값이 음수일 경우를 뜻한다.

그래서 이렇게 고쳤더니 정답.

#include <iostream>
#include <algorithm>
using namespace std;
int intmin = -2100000000;
int main() {
	int N;
	cin >> N;
	int sum = 0, result = intmin;
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		if (sum + num > 0) {
			sum += num;
			result = max(result, sum);
		}
		else {
			result = max(result, sum + num);
			sum = 0;
		}
	}
	cout << result << endl;
	return 0;
}

if else 구문을 합쳐서

result = max(result, sum += num);

if (sum < 0) sum = 0;

이렇게 만들 수 있겠지만 가독성이 좀 떨어질듯