[알고리즘] 네트워크 선 자르기(Bottom-Up)
(문제) 네트워크 선 자르기(Bottom-Up)
현수는 네트워크 선을 1m, 2m의 길이를 갖는 선으로 자르려고 합니다.
예를 들어 4m의 네트워크 선이 주어진다면
의 5가지 방법을 생각할 수 있습니다. (2)와 (3)과 (4)의 경우 왼쪽을 기준으로 자르는 위치가 다르면 다른 경우로 생각한다.
그렇다면 네트워크 선의 길이가 Nm라면 몇 가지의 자르는 방법을 생각할 수 있나요?
입력설명
첫째 줄은 네트워크 선의 총 길이인 자연수 N(3≤N≤45)이 주어집니다.
출력설명
첫 번째 줄에 부분증가수열의 최대 길이를 출력한다.
테스트케이스
입력예제 | 출력예제 |
---|---|
9 | 55 |
30 | 1346269 |
33 | 5702887 |
40 | 165580141 |
45 | 1836311903 |
해결방법
우선 기준을 1cm 와 2cm 만 된다는 가정이기 때문에, 끝에 부분을 1cm 자른다는 가정을 통해 나머지가 몇센치 남았는지 확인한다. 그리고 끝에 부분을 2cm 자른다는 가정을 통해 나머지가 몇센치 남았는지 확인한다.
그러면 그 남은 센치미터에서 구해지는 경우의 수를 더한다!
점화식을 이용해서 만든다!
f(1) = 1 f(2) = 2 f(n) = f(n-1) + f(n-2)
만들 경우 1차원 배열을 하나 만들어서 그 배열을 반복하여 결과 값을 도출한다.
코드
n = int(input())
dy = [0] * (n+1)
dy[1] = 1
dy[2] = 2
for i in range(3, n+1):
dy[i] = dy[i - 1] + dy[i - 2]
print(dy[n])
댓글남기기