[코딩테스트 C++] 1, 2, 3 더하기

오늘의 문제

https://www.acmicpc.net/problem/9095

1, 2, 3 더하기

나의 풀이

// 1, 2, 3 더하기
int solution(int t){
    vector<int> n(3, 0);
    n[0] = 1;
    n[1] = 2;
    n[2] = 4;
    if(t <= 3)
        return n[t-1];
    for(int i=4;i<=t;i++){
        int sum = n[0] + n[1] + n[2];
        n[0] = n[1];
        n[1] = n[2];
        n[2] = sum;
    }
    return n[2];
}

풀이 법

• 입력값의 범위가 11까지길래 그냥 전에 dp로 했더니 메모리 초과가 났다.
• 전에 풀어봤던 피보나치와 같은 로직이길래 3개짜리 피보나치로 풀었다.
• 하나 실패했던건 0, 1, 2인 경우 반환을 미리 안해줬기 때문 ㅎㅎ

모범 답안

#include <cstdio>
int t[11] = {0,1,2,4,7,13,24,44,81,149,274};
int main() {
	int n,x;
	scanf("%d", &n);
	while (n--) {
		scanf("%d", &x);
		printf("%d\n",t[x]);
	}
	return 0;
}

배울 점

• 아무리 범위가 적어도 그렇지 이건..ㅋㄷㅋㄷ..