문제

문제 링크

어떻게 접근할 것인가

  • 일단 1, 2, 3의 값을 넣어주고 각 숫자의 경우의 수를 DP를 이용해서 저장하면서 풀어간다.
  • 예를 들어, 5라고 하면 4 + 1, 3 + 2, 2 + 3, 1 + 4 네 경우가 가능하다 하지만 4를 더하는 것을 불가능하기 때문에 4, 3, 2를 만드는 경우의 수를 다 더해준다.

코드

#include <cstdio>

int t, n, sum[11];

int main(){
    sum[1] = 1, sum[2] = 2, sum[3] = 4;
    for(int i = 4; i < 11; i++)sum[i] = sum[i - 1] + sum[i - 2] + sum[i - 3];
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        printf("%d\n", sum[n]);
    }
}

느낀점

  • 역시 디피 시작부터 쉽지 않다. 진혁이는 금방 풀던데 참 나는 수학머리가 좀 부족한가보다.
  • 오늘은 디피로 조진다.