[백준] 1912번: 연속합 (C언어)

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

1912번: 연속합

난이도: solved.ac 실버 2

 

 

학교 알고리즘 수업 시간에 배웠던 문제다

우선 내가 짠 코드는 아래와 같다

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
 
int dp[100000];
int arr[100000];
 
int main() {
	int n, i;
	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", &arr[i]);
	int max = arr[0];
	dp[0] = arr[0];
	if (dp[0] < 0)
		dp[0] = 0;
	for (i = 1; i < n; i++) {
		dp[i] = dp[i - 1] + arr[i];
		if (dp[i] > max)
			max = dp[i];
		if (dp[i] < 0)
			dp[i] = 0;
	}
	printf("%d", max);
	return 0;
}

 

급하게 푸느라 if(dp[0] < 0) ←←← 이 부분이

for문 내의 if(dp[i] < 0)와 겹쳤다

아래는 다른 분의 코드를 참고해 다시 작성한 코드인데

이게 더 변수를 덜 사용하고 중복된 내용이 없는 것 같아 좋아보인다

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
 
int arr[100000];
 
int main() {
	int n, i;
	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", &arr[i]);
	int max = arr[0];
	for (i = 1; i < n; i++) {
		if (arr[i - 1] > 0) arr[i] = arr[i] + arr[i - 1];
		if (arr[i] > max) max = arr[i];
	}
	printf("%d", max);
	return 0;
}

 

이건 부분합을 구하는 카데인 알고리즘(Kadane's Algorithm)이라고 한다

 

그냥 하나씩 막 더하다가 합(sum)이 음수가 되면

reset을 하고 i + 1번째 항부터 다시 새로 더하는 알고리즘이다

위의 코드에서는 for문 내의 첫 번째 if문에서

i - 1항까지의 합이 양수이면

원래 arr[i]의 값과 이전까지의 합을 더한 값을 arr에 덮어씌우는 방식으로

arr[i]에 합을 나타내었다