[백준 9095] 1,2,3 더하기 (C++)

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

- 입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

- 출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

- 풀이

1,2,3 까지 구할수 있는 경우를 생각해보자.

- 1 

1

- 2 

1+1

2

- 3

1+1+1

1+2

2+1

이제 4를 생각해보면, 3에서 구했던 값들에 1을 더하고, 2에서 구했던 값들에 2를 더하고, 1에서 구했던 값들에 3을 더하면 된다.

1+1+1+1

1+2+1

2+1+1

=> dp(3)의 갯수와 동일

1+1+2

2+2

=> dp(2)의 갯수와 동일

1+3

=> dp(1)의 갯수와 동일

따라서, 점화식은 dp[n] = dp[n-1] + dp[n-2] + dp[n-3] (n >= 4)로 세울 수 있겠다.

- 코드

#include <iostream>
#include <vector>
 
#define endl "\n"
int T;
std::vector<int> dp;
 
void input_faster()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
}
void input()
{
    input_faster();
    std::cin >> T;
    dp.resize(11, 0);
}
 
void print_val(int n)
{
    std::cout << dp[n] << endl;
}
 
void solve()
{
    int n;
    int i = 3;
 
    std::cin >> n;
 
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    while (++i <= n)
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
    print_val(n);
}
 
int main()
{
    input();
    while(T--)
        solve();
    return (0);
}