[백준 2024/03/20] 9461번 파도반 수열

https://www.acmicpc.net/problem/9461

9461번: 파도반 수열

 

1. 접근 방법

이 문제에 대해서 조금 생각을 해보니, 방금 전에 생긴 삼각형에 대해서는 변으로 사용할 수 없다는 점이었다.

 

즉,

 

이렇게 변이 1인 삼각형 2개를 이용해서 생긴 새로운 변이 2인 삼격형의 경우, 연결되어 있는 변이 없기 때문에, 연결을 진행시킬 수 없다.

이런 개념을 이용하게 된다면, 

 

1 1 1 2 2 3 4 5 7 9 12의 경우 자신의 길이의 전과 전전을 더한 값이 된다는 것을 알 수 있다.

 

이런식으로 진행됨을 알 수 있다.

 

이를 기반으로, 

dict_t[x] = triangle(x - 2) + triangle(x - 3)

 

x 값을 구하기 위해서 x-2 와 x-3의 값을 더해줘야 함을 명시해 주었다.

또한 memoization을 이용해서, 중복된 계산을 피하고자 하였다.

 

2. 코드

dict_t = {1: 1, 2: 1, 3: 1, 4: 2, 5: 2, 6: 3}


def triangle(x):
    if x in dict_t:
        return dict_t[x]
    dict_t[x] = triangle(x - 2) + triangle(x - 3)
    return dict_t[x]


for i in range(int(input())):
    print(triangle(int(input())))