문제 출처 : www.acmicpc.net/problem/9461
9461번: 파도반 수열
오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의
www.acmicpc.net
문제 해석 : 가장 큰 변을 가지는 삼각형을 계속해서 이어 붙인다. 이때 N 번째 삼각형의 한번의 길이를 구하라. (삼각형은 정삼각형이다.)
문제 풀이 : 전형적인 DP 문제로서 P[i] = P[i-3] + P[i-2] 이다.
풀이 코드
T = int(input())
for test_case in range(T):
N = int(input())
P = [0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9]
answer = 0
if N <= 10:
answer = P[N]
else:
i = 11
while i <= N:
P.append( P[i-2] + P[i-3] )
i += 1
answer = P[N]
print(answer)author : donghak park
contact : donghark03@naver.com
## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.
'📊알고리즘, 문제풀이 > 📈문제풀이 (PS)' 카테고리의 다른 글
| [알고리즘][Python] 백준 11286 절댓값 힙 문제 풀이 (0) | 2021.01.15 |
|---|---|
| [알고리즘][Python] 백준 10026 적록색약 문제 풀이 (0) | 2021.01.14 |
| [알고리즘][Python] 백준 9375 패션왕 신해빈 문제 풀이 (0) | 2021.01.14 |
| [알고리즘][Python] 백준 9205 맥주 마시면서 걸어가기 문제 풀이 (0) | 2021.01.14 |
| [알고리즘][Python] 백준 9019 DSLR 문제 풀이 (0) | 2021.01.14 |