[백준/BOJ] 11659번: 구간 합 구하기 4 ( 동적 계획법 ) - C++ 문제 풀이

 

문제 설명

 

문제 링크: https://www.acmicpc.net/problem/11659

 

 

풀이

N개의 숫자로 이루어진 수열에서 부분 구간의 합을 구하는 문제입니다.

 

언뜻 보면, 언어의 사용법을 묻는 듯한 문제처럼 보입니다.

for( int i = a; i <= b; i++ ){	// a ~ b 구간의 합을 구한다
	sum += num[i];
}

그러나 이런 식으로 문제를 풀면, 제시한 시간이 아주 짧기 때문에 시간제한에 걸립니다.

 

이 문제는 발상의 전환을 한다면 쉽게 해결할 수 있습니다.

 

5 ~ 7 번째 숫자들의 합 구하기

 

만약 7개의 숫자가 제시되었을 때, 5번째부터 7번째까지 숫자의 합을 구하는 경우를 생각해 봅시다.

그럼, 위의 그림처럼 녹색 부분의 숫자의 합을 구하는 방법이 있지만, 전체의 합에서 흰색 부분 숫자의 합을 빼는 방법도 있습니다.

 

다른 말로 하면, 7번째까지 숫자의 합에서 4번째까지 숫자의 합을 뺀 값을 구하는 문제가 됩니다.

그리고, 숫자를 입력받을 때마다 배열에 저장해 둔 이전의 합과 이번 입력받은 숫자의 합을 저장하면, 필요한 숫자의 합을 쉽게 구할 수 있습니다.

 

이렇게, 이전 단계의 결과 값을 저장하고, 이 값을 재사용함으로써 다음의 문제를 해결하는 방법을 동적 계획법이라고 합니다.

 

#define SIZE    100000
int num[SIZE+1];

int main(){

    int N, M, a, b;
    cin >> N >> M;
    
    for( int i = 1; i <= N; i++){
        cin >> a;
        num[i] = a + num[i-1];  // 이번까지의 숫자의 합을 저장한다.
    }

    for( int i = 0; i < M; i++){
        
        cin >> a >> b;	// 구해야할 a ~ b 구간

        int partial = num[b] - num[a-1];	// 부분합
        
        cout << partial << "\n";
    }

    return 0;
}

이 방식의 장점은 어떤 구간이 주어지더라도 필요한 값들이 이미 저장되어 있기 때문에 수행 시간이 늘어나지 않는 점입니다.

 

 

소스 코드

#define SIZE    100000

int num[SIZE+1];

int main(){

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, M, a, b;
    cin >> N >> M;
    
    for( int i = 1; i <= N; i++){
        cin >> a;
        num[i] = a + num[i-1];  // 값을 누적시킨다.
    }

    for( int i = 0; i < M; i++){
        
        cin >> a >> b;

        int partial = num[b] - num[a-1];	// 부분합
        
        cout << partial << "\n";
    }

    return 0;
}