백준 온라인 저지, 다이나믹프로그래밍 / 9095번: 123더하기 (파이썬 / 백준 골드문제)

문제

정수 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==

접근 방법

- n이 4이상일 때, 다음과 같이 식을 추론할 수 있다. an = (1 + an-1) + (2 + an-2) + (3 + an-3)
- n이 4이상일 때, n을 1, 2, 3의 합으로 나타내는 방법은 다음과 같이 표현할 수 있다. An = A(n-1) + A(n-2) + A(n-3)
- 위의 일반항을 토대로 다이나믹 프로그래밍을 진행한다.

코드

# https://www.acmicpc.net/problem/9095 # 접근 방법 # n이 4이상일 때, 다음과 같이 식을 추론할 수 있다. an = (1 + an-1) + (2 + an-2) + (3 + an-3) # n이 4이상일 때, n을 1, 2, 3의 합으로 나타내는 방법은 다음과 같이 표현할 수 있다. An = A(n-1)  + A(n-2) + A(n-3) # 위의 일반항을 토대로 다이나믹 프로그래밍을 진행한다. def find_count(n):     if d[n]:         return d[n]     d[n] = find_count(n-1) + find_count(n-2) + find_count(n-3)     return d[n]  d = [0 for _ in range(11)] d[1] = 1 d[2] = 2 d[3] = 4 tc = int(input()) for _ in range(tc):     n = int(input())     print(find_count(n))