[Baekjoon]백준 9461 파도반 수열(실버 3) - Python

문제설명

문제를 살펴보면 10개의 숫자가 미리 주어져있고 규칙을 찾는것이 핵심인 문제이다

그림을 살펴보면 기존에 존재하는 삼각형을 서로 겹친 후에 그 중에서 긴 변을 하나의 변으로 삼아

또 다른 삼각형을 만들어가는 과정을 반복하게 된다

즉, 이전에 사용한 삼각형의 변의 길이를 서로 더하기 때문에 언제 어느시점의 삼각형을 더하는지 찾아야한다

 

주어진 10개의 숫자를 보며 규칙을 찾아보면 i번째 index의 값은 i-2번째 index의 값과 i-3번째 index의 값을 더한 것이다

이를 이용하여 코드를 작성하면 된다

여기서 주의할 점은 N을 입력받을때마다 계산하게 된다면 T의 케이스가 많을 경우 많은 시간 낭비가 일어나기 때문에

미리 값을 저장해놓은 리스트를 만들어두는게 더 좋다 문제에서 N의 범위도 주어져있기때문에 미리 만들수있다

triangle_len = [0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9]

for i in range(11, 101):
    plus = triangle_len[i - 3] + triangle_len[i - 2]
    triangle_len.append(plus)
    
T = int(input())
for _ in range(T):
    N = int(input())
    print(triangle_len[N])

0을 넣은 이유는 문제에서 시작 index가 1이기 때문에 0에 해당하는 위치에 값이 없다면

그로 인해 연산이 헷갈릴 수 있기 때문에 편의를 위하여 0을 넣어주었다

이외에는 위에서 설명한 대로 코드를 작성하였다