[백준] 1912번 - 연속합 (C++)

문제

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

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

---

입력

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

---

출력

첫째 줄에 답을 출력한다.

---

예제 입력 1 복사

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

예제 출력 1 복사

33

예제 입력 2 복사

10
2 1 -4 3 4 -4 6 5 -5 1

예제 출력 2 복사

14

예제 입력 3 복사

5
-1 -2 -3 -4 -5

예제 출력 3 복사

-1

 

---

풀이과정

이전에 풀려고 했었는데 실패했었던 문제를 이번에 새롭게 풀어보는 시간을 가졌었습니다.

이전에 군대에 들어가기전 3년전쯤에 도전했다가 틀리고 모르겠다하고 안건드렸었던 문제였었는데 이번에 다시 도전하게 되었습니다.

#include <stdio.h>

int a[100000];

int main(void) {
	
	int n, i, j, num = 0, b = -1000;
	scanf("%d", &n);
	for(i = 0;  i < n; i++) {
		scanf("%d", &a[i]);
	}
	for(i = 0; i < n; i++) {
		if(b < a[i]) b = a[i];
		if(a[i] > 0) {
			num = 0;
			for(j = i; ; j++) {
				if(a[j] >= 0 && j <= n)
					num += a[j];
				else break;
			}
			if(b < num) b = num;
		}
	}
	printf("%d", b);
	
	return 0;
}

이전에 만들었던 코드를 보니 모든 경우의 수를 컴퓨터로 직접돌릴려고하고 너무 어렵게 생각을 해서 2중for문까지 사용해가며 풀려고 했던거 같습니다. 그래서 지금 다시 문제를 봐보니 

시간제한이 1초에 추가시간없음이 나와있는거를 보니 복잡하게 생각할 필요없이 로직을 최대한 간단하게 구성을 해도 풀 수 있다는 점을 보고 어떻게해야 식을 간단하게 구성하고 풀 수 있을까는 고민해봤었습니다.

그래보니 진짜 복잡하게 생각할 필요없이 문제를 접근하면 풀 수 있는다는 점을 깨닫고 새롭게 코드를 구성하여 해결하였습니다. 

code

#include <iostream>

int		main(void)
{
	int n, temp;
	long long max = -1001, sum = 0;
	std::cin >> n;
	for(int i = 0; i < n; i++) {
		std::cin >> temp;
		sum += temp;
		if (max < sum) max = sum;
		if (sum < 0) sum = 0;
	}
	std::cout << max;

	return (0);
}

---

후기

조금 더 쉽고 간단하게 생각했으면 금방 풀었을 문제인거같은데 접근을 너무 어렵게 다가가서 더 힘들었던 거 같다.

로직을 조금 더 깊게 생각을 해서 어떻게 해야 가장 좋은 로직을 새울 수 있을지 고민을 해봐야할 것 같다.