[알고리즘]파도반 수열(백준 9461 /파이썬)

필요한 개념:동적계획법

[문제]

 

 

[문제 해결방법]

이 문제는 삼각형의 변의 길이를 가지고 규칙을 찾아서 문제를 해결하는 방법입니다.

 

숫자가 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 이런 식으로 커지는 것을 알 수 있습니다.

여기서 찾은 규칙은 

n번째의 숫자를 구하려면 n-2와 n-3을 더해야 한다는 것입니다.

수학적인 정의로 나타내면

P(n)=p(n-3)+P(n-2)

 

예를 들면 6번째 삼각형의 변의 길이를 구하려면

4번째와 3번째 삼각형의 변의 길이를 더하면

6번째 정삼각현의 길이가 나온다는 것을 할 수 있습니다.

 

P(6)=p(3)+P(4)

  3=1+2

 

그리고 숫자를 계산하면서 중복되는 값들이 나올 수 있기 때문에 

중복된 값들을 바로 사용할 수 있도록 딕셔너리를 만들어

동적 계획법을 사용하여 계산하는 시간을 줄여줍니다.

 

[코드리뷰]

이를 바탕으로 코드를 짜게 되면

먼저 값을 받고 아까 말한 규칙으로 값을 찾을 수 없는

1,2,3까지의 값을 적어 줍니다.

import sys
t = int(sys.stdin.readline())
memo={1:1, 2:1, 3:1}

그리고 재귀  함수를 사용하여

찾은 규칙을 코드로 만들어 줍니다.

def number(a):
    if a in memo: 
        return memo[a]
 #만약에 그 값이 memo에 들어가 있다면 그 값을 반환합니다
    else:
        count = number(a-2)+number(a-3)
        #if조건을 충족하지 않는다면 아까 말한 규칙을 코드로 만들어 줍니다.
        memo[a]=count
        return count
        그리고 그 계산값을 count에 반환합니다.

그리고 t줄의 수만큼 for문을 돌려서 

number 재귀 함수로 계산하여 값을 출력합니다.

for i in range(t):
    n = int(sys.stdin.readline())
    print(number(n))

[결과]