네트워크 선 자르기(Bottom-Up) - Python

<문제>

현수는 네트워크 선을 1m, 2m의 길이를 갖는 선으로 자르려고 합니다. 예를 들어 4m의 네트워크 선이 주어진다면,

의 5가지 방법을 생각할 수 있습니다. (2)와 (3)과 (4)의 경우 왼쪽을 기준으로 자르는 위치가 다르면 다른 경우로 생각한다.
그렇다면 네트워크 선의 길이가 Nm라면 몇 가지의 자르는 방법을 생각할 수 있나요?

▣ 입력설명
첫째 줄은 네트워크 선의 총 길이인 자연수 N(3≤N≤45)이 주어집니다.

 

▣ 출력설명
첫 번째 줄에 부분증가수열의 최대 길이를 출력한다.

▣  입력예제 1

7

 

▣  출력예제 1

21

<풀이>

일단 최근까지 DFS 문제를 풀었기때문에 문제를 읽자마자 DFS가 생각이나서 DFS로 풀어봤다.(DP로도 풀었음)

(풀이1)

일단 DFS로 설명하자면노드값에 n값을 넣고 -1 할때와 -2할때 를 나눠서 트리를 구현하면된다.(사실 문제가 쉬워서 크게 어려울 꺼 없다) n이 0보다 크게끔만 돌아가게 하면 아무 문제없음

(풀이2)

DP방식으로 하면 우선 DP가 점화식을 세워서 푸는 것과 매우 유사하게(어쩌면 같을지도) 문제를 해결하는데 이 문제의 경우 나는 주어진 선이 0일때는 나눌수 없으므로 방법은 1가지,  주어진 선이 1일때는 1 방법은 2가지 주어진 선이 2일때는 방법은 2가지, 주어진 선이 3개 일경우 방법은 3가지 이렇게 된다 여기서 규칙을 찾으면 주어진 선의 길이에서 방식의 수는 그전길이와 그전전길이의 방식을 구하는 수를 합한 것과 같다는 것을 알 수 있다. 즉 위 예시로 주어진 선의 길이가 3일때, 방식이 3가지인 이유는 주어진 선의길이가 2 일때 방식은 2가지 이고 주어진 선의 길이가 1일때 방식은 1가지 이므로 1+2 = 3 된다 마찬가지로 문제 예시의 4도 3 + 2 가 되서 5가 된다

이러한 방식을 이용해서 점화식을 세우고 이것을 코드로 구현하면 답이된다.

 

<코드1>

# DFS 방식
import sys
sys.setrecursionlimit(10**6) // 재귀함수 제한 걸기
def DFS(n):
    global cnt
    if n == 0:
        cnt += 1
    elif n > 0:
        DFS(n -1)
        DFS(n-2)

n = int(input())
cnt = 0
DFS(n)
print(cnt)

 

 

<코드2>

# DP 방식
n = int(input())

DP= [0] * (n + 1)
DP[0] = 1
DP[1] = 1
for i in range(2,n+1):
    DP[i] = DP[i-1] + DP[i-2]
print(DP[n])

 

DFS가 직관적이지만 문제에 따라서 DP방식이 시간이 더짧게 걸리고 효율적일 수 있으니 DP도 열심히 공부해놔야한다.(즉..점화식 세우는 연습도 열심히 해야한다는 뜻..)