백준 9461 - 파도반 수열 (Python)
2024. 2. 13. 07:05ㆍ알고리즘
문제
https://www.acmicpc.net/problem/9461
9461번: 파도반 수열
오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의
www.acmicpc.net
풀이
n = int(input())
memo = {}
memo[1] = 1
memo[2] = 1
memo[3] = 1
memo[4] = 2
memo[5] = 2
def a(i):
if i not in memo:
memo[i] = a(i-1) + a(i-5)
return memo[i]
for i in range(n):
print(a(int(input())))단순한 DP 문제이다.
N이 1~5일때는 딱히 규칙이 없는 것 같고,
N이 6 이상일때는 N-1번째 삼각형과 N-5번째 삼각형의 변의 길이를 합친 값이 N번째 삼각형의 변의 길이가 되는 것을 주어진 그림을 통해 확인할 수 있다.
memo라는 배열을 만들어 놓고 재귀함수와 memoization을 사용하여 풀이하였다.