연속합1(1912) & 연속합2(13398)
문제를 풀때 접근방법
문제를 해결하는 방법을 떠올리는게 중요하다. 이 문제를 풀때 다음과 같은 어려움에 봉착했었다.
인덱스 에서 까지 보다, 까지 연속합이 더 크면 어쩌지? 혹은 에서 까지보다 에서 까지가 더 크다면?
그런데 다이나믹프로그래밍을 사용하면 이러한 걱정이 사라진다. 배열에 입력된 수열의 각 인덱스에 해당 숫자를 포함하는 가장 큰 연속합을 저장하면 되기 때문이다. 코드는 다음과 같다.
int a[100001]; // 입력된 수열을 저장한 배열
int d[100001]; // 연속합을 저장할 배열
for(int i = 1; i <= n; i++){
d[i] = d[i]
if(d[i-1] + a[] > d[i]){
d[i] = d[i-1] + a[i];
}
}
예제와 함께 확인해보면, 배열 a
개 {5, -1, 5}
일때,
a[0]
까지의 연속합d[0]
은 이다.a[1]
까지의 연속합은d[0]
까지의 연속합 와a[1]
의 합인 4이다.a[2]
까지의 연속합은d[1]
까지의 연속합 와a[2]
의 합인 9이다.
만약 연속합 d[1]
보다 a[2]
가 큰 경우 d[2]
는 a[2]
가 된다. 그러므로, 인덱스 이후의 연속합은 d[2]
이전을 신경쓸 필요가 없다.(항상 이전 인덱스는 가장 큰 연속합을 저장하고 있다)
이제 연속합2는 쉽다.
같은 방법으로 풀면되는데 이때 수 하나를 제외할 수 있다는 옵션이 추가되었을 뿐이다.
int a[100001];
int d[100001];
int reversed[100001]; // 반대 방향의 연속합을 저장한 배열
int MAX = INT_MIN;
int sum;
for (int i = 1; i <= n; i++){
sum = 0;
if(i > 1){
sum += d[i-1];
}
if(i < n){
sum += reversed[i+1];
}
if(sum < sum + a[i]) sum += a[i]; // 현재 인덱스 값을 포함하는지 여부.
if(sum < d[i]) sum = d[i]; // i를 포함한 정방형 연속합
// if(sum < reversed[i]) sum = reversed[i]; // 이것은 필요가 없다.
if(MAX < sum) MAX = sum;
}