7-5. 동적 계획법 예제 문제 - #4. 강화하기

1. 강화하기

+1, +2, +3 만큼 강화되는 아이템이 +N강에 도달하는 경우의 수를 구하는 문제이다.

 

2. 코드 분석

#include <iostream>
#include <windows.h>
#include <vector>

using namespace std;

// 강화하기
// +1, +2, +3 중 하나씩 강화되어 +N에 도달하는 경우의 수 구하기

int cache[100];
int N;
 
// num에서 시작해서 +N 까지 가는 경우의 수
int Enchant(int num)
{
	// 예외 사항
	if (num > N)
		return 0;
	if (num == N)
		return 1;


	// 캐시 확인
	int& ret = cache[num];
	if (ret != -1)
		return ret;

	// 문제 풀이
	return ret = Enchant(num + 1) + Enchant(num + 2) + Enchant(num + 3);
}


int main()
{
	N = 9;
	memset(cache, -1, sizeof(cache));
;	cout << Enchant(0);
}

 

(1) 기본 구조

Enchant 함수는 +num강 부터 시작해서 +N강 까지 이르는데의 경우의 수를 구하는 함수이다. 

1과 2와 3을 적절히 더해서 N에 도달하는 것이 목표이므로, 강화 숫자가 N을 넘어서면 안된다.

즉 정확히 강화가 N강이 되면 1씩 늘어나는 원리이다.

+1 강화, +2 강화, +3 강화의 경우의 수를 모두 더한 것이 최종 결과이다.