[코딩테스트 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는 이전 값만 있기 때문에 가능하다.
Author And Source
이 문제에 관하여([코딩테스트 C++] 연속합), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@huijae0817/코딩테스트-C-연속합저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)