[백준] 11659번 구간 합 구하기 4 - C++ (동적계획법)

발상

1. 우선 메모이제이션할 배열 dp와 숫자를 받을 배열 array를 선언한다.

2. 각 dp[i] 에는 1부터 i까지의 합을 저장한다.

3. sum 함수를 이용해 합을 구한다. 이 때, dp[i] 가 저장되어 있으면 (-1이 아니라면) dp[i] 값을 불러오도록 하고,  저장되어 있지 않으면 dp[i] 값을 새로 구한다. 

dp[0]일 경우 0을. 아닐 경우 sum[k-1]에 arr[k-1] 값을 더한 것을 return한다. (k-1인 이유는 index의 숫자가 하나 작기 때문)

 

소스코드

#include <stdio.h>
int dp [100001];
int arr[100001];
int sum (int k){
	if (dp[k] != -1) return dp[k];
	if (k == 0) dp[k] = 0;
	else dp[k] = sum(k-1)+arr[k-1];
	return dp[k];
}
int main(){
	int N, M;
	scanf("%d %d", &N, &M);
	for(int i=0; i<N; i++){
		scanf("%d", &arr[i]);
	}
	for(int i=0; i<100001; i++){
		dp[i] = -1;
	}
	for (int l=0; l<M; l++){
		int i, j;
		scanf("%d %d", &i, &j);
		printf("%d\n", sum(j) - sum(i-1));	
	}
}

 

동적계획법 함수만 따로 보면 다음과 같다. 

int sum (int k){
	if (dp[k] != -1) return dp[k]; //-1이 아닐 경우 기존 값 불러오기
	if (k == 0) dp[k] = 0; // base case : 0일 경우 0을 return
	else dp[k] = sum(k-1)+arr[k-1]; //점화식 구현
	return dp[k];
}

 

+) 그리고 출력할 때 cin과 cout을 사용해서 시간 초과가 발생했다. 

이 문제를 해결할 때는 printf, scanf로 대체해서 일단 맞긴 했는데 

cin.tie(NULL), sync_with_stdio(false) 적용을 통해 해결할 수 있는 거였다. 

또 endl은 시간이 많이 소요되니 개행문자(\n)를 써야함. 따흑 갈길이 멀다

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

15552번: 빠른 A+B

 

#include <iostream>

using namespace std;

int dp [100001];
int arr[100001];
int sum (int k){
	if (dp[k] != -1) return dp[k];
	if (k == 0) dp[k] = 0;
	else {
		dp[k] = sum(k-1)+arr[k-1];
	}
	return dp[k];
}
int main(){
	cin.tie(NULL); ios::sync_with_stdio(false);
	int N, M;
	cin >> N >> M;
	for(int i=0; i<N; i++){
		cin >> arr[i];
	}
	for(int i=0; i<100001; i++){
		dp[i] = -1;
	}
	for (int l=0; l<M; l++){
		int i, j;
		cin >> i >> j;
		cout << sum(j) - sum(i-1) << "\n";	
	}
}