ネットワーク線のトリム


作成日:2022年2月22日午後2:39

インプリメンテーションコード

# 네트워크 선 자르기 (Top-Down: 재귀, 메모이제이션)
import sys
#sys.stdin = open("in1.txt", "rt")

n = int(input())
res = []

def factorial(n): 
    return 1 if (n==1 or n==0) else n * factorial(n - 1);  

# i는 2의 개수
for i in range(0, n//2+1):
    numberOfOne = n-2*i
    res.append((numberOfOne, i))

cnt = 0
for x in res:
    if x[0] == 0 or x[1] ==0:
        cnt += 1
    else:
        cnt += factorial(x[0]+x[1])//(factorial(x[0])*factorial(x[1]))

print(cnt)

模範解答

# 네트워크 선 자르기 (Top-Down: 재귀, 메모이제이션)
import sys
#sys.stdin = open("in1.txt", "rt")

def DFS(len):
    if len == 1 or len == 2:
        return len
    else:
        if dy[len] == 0:
            dy[len] = DFS(len-2)+DFS(len-1)
        return dy[len]

if __name__ == "__main__":
    n = int(input())
    dy = [0]*(n+1) # 메모이제이션을 위한 리스트
    print(DFS(n))

注釈

  • 注釈とは、再帰が呼び出されると、同じ計算が複数回行われる場合がある.
  • 関連コンテンツhttps://www.notion.so/7-Recursion-155324f5aa204592bbcf5d0c3f2e752b#915f8c3d02dd4db3b5b4767c3f905cd0
  • このような重複動作を回避するために、アレイ上で1回動作するコンテンツが格納され、2回目の動作がなくなる.