연속합1(1912) & 연속합2(13398)

September 19, 2019

문제를 풀때 접근방법

문제를 해결하는 방법을 떠올리는게 중요하다. 이 문제를 풀때 다음과 같은 어려움에 봉착했었다.

인덱스 $0$ 에서 $n$ 까지 보다, $n+1$ 까지 연속합이 더 크면 어쩌지? 혹은 $0$ 에서 $n$ 까지보다 $1$ 에서 $n$ 까지가 더 크다면?

그런데 다이나믹프로그래밍을 사용하면 이러한 걱정이 사라진다. 배열에 입력된 수열의 각 인덱스에 해당 숫자를 포함하는 가장 큰 연속합을 저장하면 되기 때문이다. 코드는 다음과 같다.

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]은 $5$ 이다.
a[1] 까지의 연속합은 d[0]까지의 연속합 $5$ 와 a[1]의 합인 4이다.
a[2] 까지의 연속합은 d[1]까지의 연속합 $4$ 와 a[2]의 합인 9이다.

만약 연속합 d[1]보다 a[2]가 큰 경우 d[2]는 a[2]가 된다. 그러므로, 인덱스 $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;
}