[코드업 3707] 합의 개수

동적계획법이 필요한 문제들에서 return 값이 있도록 재귀함수를 설계하는 연습을 진행 중이다. 해당 문제는 전형적인 동적계획법과 재귀함수를 이용해서 간단하게 풀이가 가능한 문제였다. 

 

#include <iostream>

using namespace std;

unsigned long cache[100000];

unsigned long dfs(short number) {

    if (number == 0) {
        return 1;
    }

    if (cache[number]) {
        return cache[number];
    }
    else {
        unsigned long sum = 0;
        for (int idx = 1; idx <= number; idx++) {
            sum += cache[number - idx] = dfs(number - idx);
        }

        return sum;
    }
}

int main() {

    short number;
    cin >> number;

    cout << dfs(number) - 1 << endl;

    return 0;
}

 

요즘 고민은 알고리즘 문제를 풀면서 너무 재귀함수, 백트래킹, 동적계획법 범주에 빠져있다보니 모든 문제를 재귀함수와 캐싱전략으로 풀이하려고 하는 습관이 들어버린 점이다. 예를 들어 연속합 문제 같은 경우에는 재귀함수와 캐싱전략을 쓰면 오히려 더 미궁 속에 빠지고 만다. 자료구조를 이용해서 풀 수 있는 문제들을 연습해 볼 시간이 온 것 같다.