코딩테스트 대비/BOJ
[Baekjoon/Python] 9461번: 파도반 수열 - 효과는 굉장했다!
bluetag_boy
2021. 11. 14. 03:45
반응형
9461번: 파도반 수열
오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의
www.acmicpc.net
알고리즘 분류
- 수학
- 다이나믹 프로그래밍
SOLUTION
import sys
dp = [1,1,1,2,2] # P(1) ~ P(5)
T = int(sys.stdin.readline())
for _ in range(T):
num = int(sys.stdin.readline())
if num >= 6: # num이 6 이상일 때에는 dynamic programming을 이용해 구함
for i in range(5, num):
dp.append(dp[i-1] + dp[i-5]) # 1~5번째에는 규칙을 찾을 수 없지만 6번째이후 부터는 P(N) = P(N-1) + P(N-5)가 성립함을 알 수 있다
print(dp[num-1])
else:
print(dp[num-1])
dp = [1,1,1,2,2] # 다시 초기화