[C/C++] 백준 1806: 부분합 (누적 합 이용)

1806: 누적합 문제

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

1806번: 부분합

 

풀이!

 사실 문제 이름 자체도 부분합이고 문제 내용도 부분합이라서 "누적합"을 이용하여 문제를 풀어야겠다는 생각을 할 수 있었다.

 

부분 합(누적 합)

 부분 합이란 배열의 시작부터 현재 위치까지의 원소의 합을 구해둔 배열이다. 이렇게 부분 합을 미리 구해 놓는다면 a번째 index부터 b번째 index까지의 합을 구할 때 O(b-a)의 시간이 걸릴 것을 psum[b]-psum[a-1]을 이용하여 O(1)로 구할 수 있다. 특히 부분 합은구간합을 두번 이상 구할 때 효과적이며 배열의 길이가 길어질 수록, 구해야하는 합의 횟수가 증가할 수록 더 효과적인 알고리즘이 된다.

 

알고리즘(동작과정)

 이 문제 역시 부분 합을 이용해서 푼다면 선형시간 내에 해결이 가능하다. 이때 사용한 배열은 입력받은 수를 저장한 arr[], 누적합을 저장한 psum[], 합이 S이상이 되었을 때의 가장 짧은 길이를 저장하는 result[]가 있다. 

 먼저 아래 표와 같이 arr[]배열과 psum[] 배열을 구할 수 있다. (예제1에 있는 수를 이용)

 

	0	1	2	3	4	5	6	7	8
arr[]	0	5	1	3	5	10	7	4	9
psum[]	0	5	6	9	14	24	31	35	44
result[]	0

 

 이때 result[] 배열을 구하는 것이 중요하다. 이때 중요한 것이 right_index이다. right index란 두 부분합의 차이가 S 이상일때 큰 부분합의 index를 저장하고 다음번에 for문을 돌때 right_index부터 비교하기 시작하며 두 부분합의 차이가 S 이상인지 확인하는 것이다. 또한 부분 합의 차이가 S 이상인지 확인하는 식을 구하고 그 값을 result에 넣은 후 right_index 값을 넣어주면 된다.

 참고로 누적 합을 담은 배열은 index가 1부터 시작하는 것이 좋다. 누적합 점화식이 psum[j]-psum[i-1]인데 i가 1부터 시작하고 psum[0]=0으로 만들어둔다면 깔끔하게 식 하나로 정리가 가능하다

if(psum[j]-psum[i-1]>=target){
        result[i]=j-i+1;
        right_index=j; //다음번에 여기서부터 이중for문을 시작(시간복잡도 줄임)
        break;
      }

이 방법대로 한다면 맨 처음에  index 1일 때 두 부분합의 차이가 15 이상이기 위해서는 psum[5]-psum[0]일 때이므로 result의 길이는 5가 된다. 이때 right_index는 5에서 멈춰있다가 index 2일때 비교를 할때 5부터 비교하게 된다.

	0	1	2	3	4	5	6	7	8
arr[]	0	5	1	3	5	10	7	4	9
psum[]	0	5	6	9	14	24	31	35	44
result[]	0	5

 

 

이후 index가 2, 3, 4일때도 부분합의 차이가 15이상이므로 right_index가 5에서 머물게 된다.

	0	1	2	3	4	5	6	7	8
arr[]	0	5	1	3	5	10	7	4	9
psum[]	0	5	6	9	14	24	31	35	44
result[]	0	5	4	3	2

 

 

이후 index가 5일때 부분합의 차이가 15이기 위해 right_index가 6으로 이동한다.

	0	1	2	3	4	5	6	7	8
arr[]	0	5	1	3	5	10	7	4	9
psum[]	0	5	6	9	14	24	31	35	44
result[]	0	5	4	3	2	2

 

 

이렇게 해서 index가 8일때까지 완료하면 표는 다음과 같이 완성된다

	0	1	2	3	4	5	6	7	8
arr[]	0	5	1	3	5	10	7	4	9
psum[]	0	5	6	9	14	24	31	35	44
result	0	5	4	3	2	2	3	0	0

 

이때 result 배열에 0이 들어가 있는 경우는 그 인덱스에 해당하는 값부터의 연속된 합이 S를 넘지 못하는 경우이다.

따라서 최소인 길이를 구하기 위해서는 result[i]==0인 경우를 빼줘야 한다.

 또한 모든 경우에서 합을 S를 넘지 못할 경우 0을 출력하도록 만든다.

int min_value=100002;
  for(int i=1;i<=n;i++){
    if(result[i]==0) //여기서부터 연속된 합이 S를 못넘음
      continue;
    min_value=min(min_value,result[i]);
  }
  if(min_value==100002)
    cout<<0;
  else
    cout<<min_value;

 

 

 

 

소스코드!

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#include<queue>
#include<map>

using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역
int psum[100001];
int result[100001];

int main() {    
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n,target;
  cin>>n>>target;

  for(int i=1;i<=n;i++){
    int tmp;
    cin>>tmp;
    psum[i]=psum[i-1]+tmp;
  }
  int right_index=1;
  for(int i=1;i<=n;i++){
    for(int j=right_index;j<=n;j++){
      if(psum[j]-psum[i-1]>=target){
        result[i]=j-i+1;
        right_index=j; //다음번에 여기서부터 이중for문을 시작(시간복잡도 줄임)
        break;
      }
    }
  }
  
  int min_value=100002;
  for(int i=1;i<=n;i++){
    if(result[i]==0) //여기서부터 연속된 합이 S를 못넘음
      continue;
    min_value=min(min_value,result[i]);
  }
  if(min_value==100002)
    cout<<0;
  else
    cout<<min_value;
}