현수는 네트워크 선을 1m, 2m의 길이를 갖는 선으로 자르려고 합니다. 예를 들어 4m의 네트워크 선이 주어진다면
1) 1m+1m+1m+1m
2) 2m+1m+1m
3) 1m+2m+1m
4) 1m+1m+2m
5) 2m+2m
의 5가지 방법을 생각할 수 있습니다. (2)와 (3)과 (4)의 경우 왼쪽을 기준으로 자르는 위치가 다르면 다른 경우로 생각한다.
그렇다면 네트워크 선의 길이가 Nm라면 몇 가지의 자르는 방법을 생각할 수 있나요?
▣ 입력설명
첫째 줄은 네트워크 선의 총 길이인 자연수 N(3≤N≤45)이 주어집니다.
▣ 출력설명
첫 번째 줄에 부분증가수열의 최대 길이를 출력한다.
▣ 입력예제 1
7
▣ 출력예제 1
21
#import sys
#sys.stdin = open('in.txt', 'rt')
def DFS(L):
if a[L] > 0:
return a[L]
if L == 1 or L == 2:
return L
else:
a[L] = DFS(L-1)+DFS(L-2)
return a[L]
if __name__ == '__main__':
n = int(input())
print(f'n:{n}')
# bottom up
res = [0]*n
res[0] = 1
res[1] = 2
for i in range(2, n):
res[i] = res[i-1]+res[i-2]
print(res[-1])
# top down
a = [0]*(n+1)
cnt = DFS(n)
print(cnt)
'Algorithm > Python' 카테고리의 다른 글
075 - 돌다리 건너기(Bottom-Up) (1) | 2023.10.14 |
---|---|
074 - 계단오르기(Top-Down : 메모이제이션) (1) | 2023.10.14 |
072 - 피자 배달 거리(삼성 SW역량평가 기출문제 : DFS활용) (1) | 2023.10.14 |
071 - 사다리 타기(DFS) (1) | 2023.10.06 |
070 - 토마토(BFS 활용) (0) | 2023.10.06 |