시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 19831 12800 8856 62.871%

문제

정수 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+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWM4MTVcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIG5cdWM3NDAgXHVjNTkxXHVjMjE4XHVjNzc0XHViYTcwIDExXHViY2Y0XHViMmU0IFx1Yzc5MVx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCwgblx1Yzc0NCAxLCAyLCAzXHVjNzU4IFx1ZDU2OVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTA5NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkFkZGluZyAxcywgMnMsIGFuZCAzcyIsImRlc2NyaXB0aW9uIjoiPHA+SW50ZWdlciA0IGNhbiBiZSBleHByZXNzZWQgYXMgYSBzdW0gb2YgMXMsIDJzLCBhbmQgM3MgaW4gc2V2ZW4gZGlmZmVyZW50IHdheXMgYXMgZm9sbG93czo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4xKzErMSsxLDxcL2xpPlxyXG5cdDxsaT4xKzErMiw8XC9saT5cclxuXHQ8bGk+MSsyKzEsPFwvbGk+XHJcblx0PGxpPjIrMSsxLDxcL2xpPlxyXG5cdDxsaT4yKzIsPFwvbGk+XHJcblx0PGxpPjErMywgYW5kPFwvbGk+XHJcblx0PGxpPjMrMS48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBkZXRlcm1pbmVzIHRoZSBudW1iZXIgb2Ygd2F5cyBpbiB3aGljaCBhIGdpdmVuIGludGVnZXIgY2FuIGJlIGV4cHJlc3NlZCBhcyBhIHN1bSBvZiAxcywgMnMsIGFuZCAzcy4gWW91IG1heSBhc3N1bWUgdGhhdCB0aGUgaW50ZWdlciBpcyBwb3NpdGl2ZSBhbmQgbGVzcyB0aGFuIDExLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIChUICkgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGZpbGUuIEVhY2ggdGVzdCBjYXNlIGNvbnNpc3RzIG9mIGFuIGludGVnZXIgd3JpdHRlbiBpbiBhIHNpbmdsZSBsaW5lLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBUaGUgbGluZSBzaG91bGQgY29udGFpbiBhbiBpbnRlZ2VyIHJlcHJlc2VudGluZyB0aGUgbnVtYmVyIG9mIHdheXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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