[코딩테스트 C++] 연속합

오늘의 문제

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

연속합

접근 방법

• 연속으로 된 합 중 가장 큰것을 출력하는 것이 목표.
• 입력값이 100000이므로 최대 O(NlongN)의 알고리즘을 작성하면 된다.
• dp를 사용하면 O(N)만에 문제를 풀 수 있다.
• 간단하게 합을 구해, 저장하되, 합이 원래의 값보다 작은경우 큰 원래값을 저장한다.
• 결과 중 가장 큰 값을 출력한다.
• 왜 그렇냐면, 연속으로 더하는데, 작아지는 부분이 존재하면, 거기서부터 끊고 다음에는 반영하지 않아야한다.
• 오른쪽이 가장 큰 값이면, 왼쪽에 작아지는 부분이 있으면 무조건 제일 큰 값보다 작아지기 때문.

나의 풀이

#include <iostream>
using namespace std;
const int MAX = 100000;
int arr[MAX+1] ={0, };
int dp[MAX+1] ={0, };
int n;

int solution(){
    int answer = arr[1];
    for(int i=1;i<=n;i++){
        dp[i] = max(dp[i-1] + arr[i], arr[i]);
        answer = max(answer, dp[i]);
    }
    return answer;
}

다른 풀이

#include<iostream>
using namespace std;
int main() {
	int N,max=-1000;
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	cin>>N;
	for(int i=0,t=0,b;i<N;i++){
		cin>>b;
		b=t+b>b?t+b:b;
		max=max<b?b:max;
		t=b;
	}
	cout<<max;
}

배울 점

• 다른풀이를 보면, 입력에서 시간을 줄이는 방법이 참 많은걸 알게된다.
• 이분은 들어오는 값과 max만을 이용해서 문제를 풀었다. 어차피 사용되는 dp는 이전 값만 있기 때문에 가능하다.