네트워크 선 자르기 (Top-Down)
생성일: 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
- 이러한 중복되는 작업을 피하기 위해 어레이에 한번 작업한 내용은 저장을 하여 두번 작업하는 일이 없도록 하는 것을 메모이제이션이라고 한다.
Author And Source
이 문제에 관하여(네트워크 선 자르기 (Top-Down)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lsj8706/네트워크-선-자르기-Top-Down저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)