코드업 3702 파스칼의 삼각형

이 문제는 지난 피보나치 수열과 별반 다를게 없습니다.

피보나치 수열과 메모이제이션 해결법

거기에다가 재귀함수를 사용하지만 시간초과과 뜨기 때문에 메모이제이션정도만 추가를 하면 될거 같습니다.

그런데 지난번과 다른 것은 기억해야할 값이 한개가 아니라 두개라는 거지요 2차원 평면에서 값을 가져오는 것처럼 보기 때문입니다.

이때도 파이썬의 사전은 굉장히 강력하면서 간단하게 키값을 받을 수 있습니다.

키 값에다가 복잡하게 할 것도 없고 저러면 값이 나옵니다. 이거를 응용해서 코드를 봅시다.

a,b = map(int, input().split())
dic={}

def findpascal(a,b):
    if (a,b) in dic:
        return dic[a,b]
    
    if a == 1:
        dic[1,b]=1
        return 1
    if b == 1:
        dic[a,1]=1
        return 1
    else:
        dic[a,b] = findpascal(a,b-1)+findpascal(a-1,b)
        return dic[a,b]
    
print(findpascal(a,b)%100000000)

map를 이용해서 두 인수를 받아주고 메모이제이션으로 사용할 사전을 하나 만들어 줍시다.

그리고 함수는 a또는 b 그러니까 2차원 배열에서 벽에 붙은경우지요, 그럴때는 1값을 반환을하고

아닐 경우에는 저 두값을 더해서 반환을 해주면 됩니다.

출력은 숫자가 너무 커지니 나머지로 해달라고 했으니 저렇게 하면 됩니다.