1912: 연속합

네르기·2022년 9월 9일
0

알고리즘

목록 보기
68/76

어떤 문제인가?

동적 계획법을 이용해, 어떤 수열이 주어졌을 때 그 최대의 부분합을 구하는 문제.

시행착오 횟수

한 번에 성공.

1차 시도: AC

그래프를 그려보니 이 문제는 다음으로 바꿔 쓸 수 있다.

우측 끝에서 내 바로 오른쪽에 있는 원소까지의 합과 나 자신을 더한 것이 나 자신보다 큰가?

즉, 트리에 비유하자면 자기 자식을 버릴지, 그대로 들고 갈지를 묻는 문제다.
다음을 보면 이해가 빠를 것이다.

21 입장에서, 자신만 쓸 것인지 혹은 자식까지 쓸 것인지를 결정해야 하며
12 입장에서는 21 또는 21까지의 연속합 둘 중 무엇을 써야 할지를 묻는 문제가 된다.

문제에서는 가장 큰 합을 구하라고 한다. 그렇다면 기준을 세울 수 있다.
21 입장에서 보면 -1을 더하면 최대의 합을 만들 수 없으므로 버려야 한다. 자기 자신만을 써야 한다.
12는 이제 21을 들고 갈 지 버릴 지 선택할 수 있다. 당연히 21을 들고 가야 최대의 합을 만들 수 있으므로 자기 자신과 더한다.

이를 수식으로 나타내자. DiD_i를 맨 끝(n1n-1)에서 ii까지의 최대 부분합이라고 정의하자.

Di=max(Di+Di+1,  Di)where0i<nD_i = \text{max}(D_i+D_{i+1},\;D_i) \\ where \quad 0 \leq i \lt n

이렇게 구한 값 중 최댓값을 출력하면 문제를 해결할 수 있다. 본격적으로 코드로 나타내보자.

#include <stdio.h>
#define SIZE 100000
#define MIN -1000

int D[SIZE], T[SIZE];

int main() {
    int n, m=MIN;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%d", &T[i]);
    
    D[n-1] = T[n-1];
    for(int i = n-2; i>=0; i--)
        D[i] = D[i+1]+T[i] > T[i] ? D[i+1]+T[i] : T[i];
    
    for(int j = 0; j < n; j++)
        m = m < D[j] ? D[j] : m;
    printf("%d", m);
}

다른 분들의 풀이

#include <stdio.h>

int main()
{
	int n,t,sum=0,max=0x80000000;
	for(scanf("%d",&n);n--;)
	{
		scanf("%d",&t);
		sum+=t;
		if(sum>max) max=sum;
		if(sum<0) sum=0;
	}
	printf("%d",max);
	return 0;
}

-> f52985님의 풀이
DP를 이용한 풀이 원리는 '전체 합을 깎아먹는 녀석은 버린다'인데, 여기에 그 원리가 숨어있다.

profile
프로그래머와 애니메이터가 되고파

0개의 댓글