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

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

제한

 

예제 입력 1

3
4
7
10

예제 출력 1

7
44
274

힌트

 

W3sicHJvYmxlbV9pZCI6IjkwOTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiIxLCAyLCAzIFx1YjM1NFx1ZDU1OFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjODE1XHVjMjE4IDRcdWI5N2MgMSwgMiwgM1x1Yzc1OCBcdWQ1NjlcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWNkMWQgN1x1YWMwMFx1YzljMFx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1ZDU2OVx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYmMgXHViNTRjXHViMjk0IFx1YzIxOFx1Yjk3YyAxXHVhYzFjIFx1Yzc3NFx1YzBjMSBcdWMwYWNcdWM2YTlcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjErMSsxKzE8XC9saT5cclxuXHQ8bGk+MSsxKzI8XC9saT5cclxuXHQ8bGk+MSsyKzE8XC9saT5cclxuXHQ8bGk+MisxKzE8XC9saT5cclxuXHQ8bGk+MisyPFwvbGk+XHJcblx0PGxpPjErMzxcL2xpPlxyXG5cdDxsaT4zKzE8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM4MTVcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBuXHVjNzQ0IDEsIDIsIDNcdWM3NTggXHVkNTY5XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWM4MTVcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIG5cdWM3NDAgXHVjNTkxXHVjMjE4XHVjNzc0XHViYTcwIDExXHViY2Y0XHViMmU0IFx1Yzc5MVx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCwgblx1Yzc0NCAxLCAyLCAzXHVjNzU4IFx1ZDU2OVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiOTA5NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkFkZGluZyAxcywgMnMsIGFuZCAzcyIsImRlc2NyaXB0aW9uIjoiPHA+SW50ZWdlciA0IGNhbiBiZSBleHByZXNzZWQgYXMgYSBzdW0gb2YgMXMsIDJzLCBhbmQgM3MgaW4gc2V2ZW4gZGlmZmVyZW50IHdheXMgYXMgZm9sbG93czo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4xKzErMSsxLDxcL2xpPlxyXG5cdDxsaT4xKzErMiw8XC9saT5cclxuXHQ8bGk+MSsyKzEsPFwvbGk+XHJcblx0PGxpPjIrMSsxLDxcL2xpPlxyXG5cdDxsaT4yKzIsPFwvbGk+XHJcblx0PGxpPjErMywgYW5kPFwvbGk+XHJcblx0PGxpPjMrMS48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBkZXRlcm1pbmVzIHRoZSBudW1iZXIgb2Ygd2F5cyBpbiB3aGljaCBhIGdpdmVuIGludGVnZXIgY2FuIGJlIGV4cHJlc3NlZCBhcyBhIHN1bSBvZiAxcywgMnMsIGFuZCAzcy4gWW91IG1heSBhc3N1bWUgdGhhdCB0aGUgaW50ZWdlciBpcyBwb3NpdGl2ZSBhbmQgbGVzcyB0aGFuIDExLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIChUICkgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGZpbGUuIEVhY2ggdGVzdCBjYXNlIGNvbnNpc3RzIG9mIGFuIGludGVnZXIgd3JpdHRlbiBpbiBhIHNpbmdsZSBsaW5lLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBUaGUgbGluZSBzaG91bGQgY29udGFpbiBhbiBpbnRlZ2VyIHJlcHJlc2VudGluZyB0aGUgbnVtYmVyIG9mIHdheXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Taejon 2001 PC번

• 문제를 번역한 사람: baekjoon
• 문제의 오타를 찾은 사람: standardraccoon, wjrqur1200

출처

ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Taejon 2001 PC번

• 문제를 번역한 사람: baekjoon
• 문제의 오타를 찾은 사람: standardraccoon, wjrqur1200

#include <iostream>
using namespace std;
int GetResult(int N)
{
    if (N == 0)
        return 1;
    if (N < 0)
        return 0;
    return GetResult(N - 1) + GetResult(N - 2) + GetResult(N - 3);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N,input;
    cin >> N;
    while (N-- > 0)
    {
        cin >> input;
        if (input > 0)
        {
            cout << GetResult(input) << "\n";
        }
        else
            cout << "0\n";
    }
    return 0;
}