CodeUp / Recursion(재귀) / 1930번 / SuperSum / C++

SuperSumSuperSum 함수는 다음과 같이 정의된다.

 

      SuperSum(0,n)=n (n은  모든 양의 정수)

      SuperSum(k,n)=SuperSum(k−1,1)+SuperSum(k−1,2)+...+SuperSum(k−1,n)

 

k와 n이 여러개 주어진다. SuperSum의 값을 각각 출력하시오.

 

입력

k(1<=k<=14)와 n(1<=n<=14)이 입력된다. 입력의 끝은 EOF(End Of File)이다.

(입력 처리 방법)

while( scanf("%d %d", &k, &n) != EOF ) printf("%d\n", SuperSum(k, n));

 

출력

SuperSum(k,n)SuperSum(k,n)의 값을 각 행에 하나씩 출력한다.

 

입력 예시

1 3 2 3 4 10 10 10

 

출력 예시

6 10 2002 167960

 

도움말

ACM-ICPC타입의 입출력방식입니다.

입력의 개수가 몇 개인지 모릅니다. (많겠죠..?)

재귀함수 SuperSum(k, n)를 정의하는 문제이며, 메모이제이션(Memoization) 기법을 활용하면 시간을 단축시킬 수 있습니다.

 

#include <iostream>
using namespace std;

int arr[15][15] = { 0 }; // 메모이제이션

int SuperSum(int k, int n) { // k가 0일경우 n저장하고 n return
	if (k == 0) {
		arr[k][n] = n;
		return n;
	}

	if (arr[k][n]) return arr[k][n]; // 이미 값이 저장되있다면 그 값 return

	for (int i = 1; i <= n; i++) {
		arr[k][n] += SuperSum(k - 1, i);
	}

	return arr[k][n];
}

int main() {
	int k, n;

	while ((scanf("%d %d", &k, &n)) != EOF) {
		printf("%d\n", SuperSum(k, n));
	}
}

 

---

 

메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때,

이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는

기술이다.

동적 계획법의 핵심이 되는 기술이다.

 

위 문제로 보자면, 재귀를 돌면서 나온 값들을 배열에 저장해놓는 것이다.

그럼 더 큰 재귀를 돌때 처음부터 다시하는게 아니라 미리 저장해놓은 값을 참조하여 재귀를 돌기때문에,

실행시간을 단축시킬 수 있다.