백준 온라인 저지, 다이나믹프로그래밍 / 9461번: 파도반수열 (파이썬 / , 백준 실버문제)

문제

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)

출력

각 테스트 케이스마다 P(N)을 출력한다.

제한

예제 입력 1

2
6
12

예제 출력 1

3
16

힌트

W3sicHJvYmxlbV9pZCI6Ijk0NjEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzMGNcdWIzYzRcdWJjMTggXHVjMjE4XHVjNWY0IiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3BhbmRvdmFuLnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDoxODJweDsgd2lkdGg6Mjg5cHhcIiBcLz5cdWM2MjRcdWI5NzhcdWNhYmQgXHVhZGY4XHViOWJjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NzQgXHViMDk4XHVjMTIwIFx1YmFhOFx1YzU5MVx1YzczY1x1Yjg1YyBcdWIxOTNcdWM1ZWNcdWM4MzggXHVjNzg4XHViMmU0LiBcdWNjYWIgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzQwIFx1YzgxNVx1YzBiY1x1YWMwMVx1ZDYxNVx1YzczY1x1Yjg1YyBcdWJjYzBcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IDFcdWM3NzRcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGNcdWM1ZDBcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWFjZmNcdWM4MTVcdWM3M2NcdWI4NWMgXHVjODE1XHVjMGJjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1YWNjNFx1YzE4ZCBcdWNkOTRcdWFjMDBcdWQ1NWNcdWIyZTQuIFx1YjA5OFx1YzEyMFx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVhZTM0IFx1YmNjMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2Mga1x1Yjc3YyBcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWFkZjggXHViY2MwXHVjNWQwIFx1YWUzOFx1Yzc3NFx1YWMwMCBrXHVjNzc4IFx1YzgxNVx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWNkOTRcdWFjMDBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDMwY1x1YjNjNFx1YmMxOCBcdWMyMThcdWM1ZjQgUChOKVx1Yzc0MCBcdWIwOThcdWMxMjBcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzgxNVx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWJjYzBcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzc0XHViMmU0LiBQKDEpXHViZDgwXHVkMTMwIFAoMTApXHVhZTRjXHVjOWMwIFx1Y2NhYiAxMFx1YWMxYyBcdWMyMmJcdWM3OTBcdWIyOTQgMSwgMSwgMSwgMiwgMiwgMywgNCwgNSwgNywgOVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+Tlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBQKE4pXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFAoTilcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6Ijk0NjEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQYWRvdmFuIFNlcXVlbmNlIiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3BhbmRvdmFuLnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDoxODJweDsgd2lkdGg6Mjg5cHhcIiBcLz5Db25zaWRlciB0aGUgc3BpcmFsIG9mIHRyaWFuZ2xlcyBzaG93biBpbiBGaWd1cmUgMS4gSXQgc3RhcnRzIHdpdGggYW4gZXF1aWxhdGVyYWwgdHJpYW5nbGUsIHRoYXQgaXMsIGEgdHJpYW5nbGUgd2hvc2Ugc2lkZSBsZW5ndGhzIGFyZSB0aGUgc2FtZSwgb2Ygc2lkZSBsZW5ndGggMSBhbmQgaXQgaXMgZXh0ZW5kZWQgYnkgYWRkaW5nIGVxdWlsYXRlcmFsIHRyaWFuZ2xlcyByZXBlYXRlZGx5IGFzIGZvbGxvd3M6IEFuIGVxdWlsYXRlcmFsIHRyaWFuZ2xlIG9mIHNpZGUgbGVuZ3RoIGsgaXMgYWRkZWQgdG8gdGhlIGxvbmdlc3Qgc2lkZSBvZiBhIHNwaXJhbCwgd2hlcmUgayBpcyB0aGUgbGVuZ3RoIG9mIHRoZSBsb25nZXN0IHNpZGUgb2YgdGhlIHNwaXJhbC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlbiwgdGhlIFBhZG92YW4gc2VxdWVuY2UgUChOKSBpcyB0aGUgc2VxdWVuY2Ugb2Ygc2lkZSBsZW5ndGhzIG9mIHRoZSBlcXVpbGF0ZXJhbCB0cmlhbmdsZXMgaW4gdGhlIHNwaXJhbC4gVGhlIGZpcnN0IDEwIHZhbHVlcyBQKDEpIHRocm91Z2ggUCgxMCkgYXJlIDEsIDEsIDEsIDIsIDIsIDMsIDQsIDUsIDcsIDkuJm5ic3A7PGJyIFwvPlxyXG4mbmJzcDs8YnIgXC8+XHJcbkdpdmVuIGEgcG9zaXRpdmUgaW50ZWdlciBOLCB3cml0ZSBhIHByb2dyYW0gdG8gY29tcHV0ZSBQKE4pLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSBjb25zaXN0cyBvZiBvbmUgbGluZSBjb250YWluaW5nIGFuIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxMDApLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBUaGUgbGluZSBzaG91bGQgY29udGFpbiBQKE4pLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

접근 방법

- 나선에서 가장 큰 변을 변으로 가지는 정삼각형을 계속 만들다보면 정삼각형 4개를 이어붙일 때부터 오각형이 된다. 이를 계속 반복하더라도 오각형의 형태는 유지한다.
- 정삼각형 5개를 이어붙인 뒤에는 가장 큰 변과 아직 하나의 변이라도 삼각형이 이어붙이지 않은 변이 있는 삼각형 중 가장 작은 변의 합으로 k가 결정된다.
- 위의 특징을 활용해 dp테이블을 만든다.

코드

# https://www.acmicpc.net/problem/9461
# 접근방법
# 나선에서 가장 큰 변을 변으로 가지는 정삼각형을 계속 만들다보면 정삼각형 4개를 이어붙일 때부터 오각형이 된다. 이를 계속 반복하더라도 오각형의 형태는 유지한다.
# 정삼각형 5개를 이어붙인 뒤에는 가장 큰 변과 아직 하나의 변이라도 삼각형이 이어붙이지 않은 변이 있는 삼각형 중 가장 작은 변의 합으로 k가 결정된다.
# 위의 특징을 활용해 dp테이블을 만든다.
dp = [0] * 101
dp[1], dp[2], dp[3], dp[4], dp[5] = 1, 1, 1, 2, 2

i = 6
while i <= 100:
    dp[i] = dp[i-1] + dp[i - 5]
    i += 1

for tc in range(int(input())):
    n = int(input())
    print(dp[n])