[C언어] 9095번 1, 2, 3 더하기 - DP

#include <stdio.h>

int memo[11];

int f(int n)
{
    switch(n) {
        case 3:
            return 4;
        case 2:
            return 2;
        case 1:
            return 1;
    }
    if(memo[n])  //이미 메모되어 있는 경우 메모되어 있는 값 반환
        return memo[n];
    return memo[n] = f(n-1)+f(n-2)+f(n-3);  //1, 2, 3의 합으로 재귀
}

int main()
{
    int T, n;  //테스트 케이스의 개수, 정수 n
    int i;
    
    scanf("%d", &T);
    for(i=0; i<T; i++) {
        scanf("%d", &n);
        printf("%d\n", f(n));
    }
    
    return 0;
}

 

그냥 간단하다. 메모리제이션으로 -1, -2, -3으로 나눠서 풀면 간단하게 얻을 수 있다.

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.