시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 15744 10346 7224 64.156%

문제

정수 4를 1, 2, 3의 조합으로 나타내는 방법은 총 7가지가 있다.

  • 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+XHVjODE1XHVjMjE4IDRcdWI5N2MgMSwgMiwgM1x1Yzc1OCBcdWM4NzBcdWQ1NjlcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWNkMWQgN1x1YWMwMFx1YzljMFx1YWMwMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MSsxKzErMTxcL2xpPlxyXG5cdDxsaT4xKzErMjxcL2xpPlxyXG5cdDxsaT4xKzIrMTxcL2xpPlxyXG5cdDxsaT4yKzErMTxcL2xpPlxyXG5cdDxsaT4yKzI8XC9saT5cclxuXHQ8bGk+MSszPFwvbGk+XHJcblx0PGxpPjMrMTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzgxNVx1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIG5cdWM3NDQgMSwyLDNcdWM3NTggXHVkNTY5XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWM4MTVcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIG5cdWM3NDAgXHVjNTkxXHVjMjE4XHVjNzc0XHViYTcwIDExXHViY2Y0XHViMmU0IFx1Yzc5MVx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCwgblx1Yzc0NCAxLDIsM1x1Yzc1OCBcdWQ1NjlcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjkwOTUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBZGRpbmcgMXMsIDJzLCBhbmQgM3MiLCJkZXNjcmlwdGlvbiI6IjxwPkludGVnZXIgNCBjYW4gYmUgZXhwcmVzc2VkIGFzIGEgc3VtIG9mIDFzLCAycywgYW5kIDNzIGluIHNldmVuIGRpZmZlcmVudCB3YXlzIGFzIGZvbGxvd3M6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MSsxKzErMSw8XC9saT5cclxuXHQ8bGk+MSsxKzIsPFwvbGk+XHJcblx0PGxpPjErMisxLDxcL2xpPlxyXG5cdDxsaT4yKzErMSw8XC9saT5cclxuXHQ8bGk+MisyLDxcL2xpPlxyXG5cdDxsaT4xKzMsIGFuZDxcL2xpPlxyXG5cdDxsaT4zKzEuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgZGV0ZXJtaW5lcyB0aGUgbnVtYmVyIG9mIHdheXMgaW4gd2hpY2ggYSBnaXZlbiBpbnRlZ2VyIGNhbiBiZSBleHByZXNzZWQgYXMgYSBzdW0gb2YgMXMsIDJzLCBhbmQgM3MuIFlvdSBtYXkgYXNzdW1lIHRoYXQgdGhlIGludGVnZXIgaXMgcG9zaXRpdmUgYW5kIGxlc3MgdGhhbiAxMS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyAoVCApIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBmaWxlLiBFYWNoIHRlc3QgY2FzZSBjb25zaXN0cyBvZiBhbiBpbnRlZ2VyIHdyaXR0ZW4gaW4gYSBzaW5nbGUgbGluZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCBleGFjdGx5IG9uZSBsaW5lIGZvciBlYWNoIHRlc3QgY2FzZS4gVGhlIGxpbmUgc2hvdWxkIGNvbnRhaW4gYW4gaW50ZWdlciByZXByZXNlbnRpbmcgdGhlIG51bWJlciBvZiB3YXlzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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