[알고리즘] 동적계획법 - Enchant

글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자입니다

 

목차

 

 

---

 

인프런 Rookiss님의 '자료구조와 알고리즘' 강의를 기반으로 정리한 필기입니다. 
😎 [C++과 언리얼로 만드는 MMORPG 게임 개발 시리즈] Part3: 자료구조와 알고리즘 강의 들으러 가기!

 

Enchant 문제

본문내용넣기

+0 집행검이 주어졌다. 집행검에 무기 강화 주문서를 사용하면 '+1, +2, +3' 중 하나만 적용된다.

이 때, +9 집행검이 뜨는 경우의 수는?

 

ex. +1, +2, +3, +4, ..., +9

ex. +3, +6, +9

ex. +1, +3, +4, ..., +9

---

해결 전략

 

해결 전략

• 강화 정도 설정 :  int N;
• 강화 횟수 설정 :  num
• 캐시 설정         :  memset(cache, -1, sizeof(cache));
• 강화 함수 설정 :  int Enchant(int num)

 

 

 

---

 

전체 코드

#include <iostream>
using namespace std;
 
int N;
int cache[100];
 
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));
 
    int ret = Enchant(0);
    cout << ret << endl;
}

 

---

 

실행