네트워크 선 자르기 (Bottom-Up)
생성일: 2022년 2월 22일 오후 2:39
구현 코드 ⭐
# 네트워크 선 자르기 (Bottom-Up)
import sys
sys.stdin = open("input.txt", "rt")
n = int(input())
dy = [0]*(n+1)
dy[1] = 1
dy[2] = 2
for i in range(3, n+1):
dy[i] = dy[i-2] + dy[i-1]
print(dy[n])
동적 계획법
- 이 문제는 동적 계획법을 사용하면 쉽게 해결 가능하다.
- 동적 계획법이란 문제를 아주 직관적으로 답을 찾을 수 있을 정도록 잘게 쪼개서 해결한 후 규칙을 찾아내서 큰 규모로 확장시킨 문제 또한 풀 수 있도록 하는 테크닉
- 일종의 점화식
- 이 문제에서는 선의 길이가 1일 때는 직관적으로 가능한 경우의 수가 1가지 (1m 한개)이고, 2일 때는 2가지(1+1, 2)임을 알 수 있다.
- 선의 길이가 3이라면 선의 길이가 1인경우의 수 + 선의 길이가 2인 경우의 수 만큼의 경우의 수가 생긴다.
- 즉, f(n) = f(n-2) + f(n-1) 이 성립한다.
- 이를 이용하여 초기 값 1과 2를 배열에 저장하고 반복문을 돌면서 값을 키웠을 때의 답도 찾아낼 수 있다.
Author And Source
이 문제에 관하여(네트워크 선 자르기 (Bottom-Up)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lsj8706/네트워크-선-자르기-Bottom-Up저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)