네트워크 선 자르기

가장 작은 해를 구하고, 점점 키워나가면서 앞에 구해놓은 해를 이용하여 현재 해를 구하고 ... n의 해를 구하고 최종적으로 필요한 해를 구한다 >> Bottom up 방식.
문제를 확장시켜서, 문제를 키워서 최종 결과를 내는 방식이다.

네트워크 선 자르기(Bottom-Up)
4m의 네트워크 선
1) 1m + 1m + 1m + 1m
2) 2m + 1m + 1m
3) 1m + 2m + 1m
4) 2m + 2m

본인 풀이

• pactorial 함수 만들어서 n(전체)! // (1 중복 개수)p! * (2 중복 개수)q! 으로 나누어 주었다.
  
  정답은 맞았지만, DP를 활용하지 않았다.

import sys

# sys.stdin=open("input.txt","rt")

def input():
    return sys.stdin.readline().rstrip()

def factorial(x):
    res = 1
    for i in range(1,x+1):
        res *= i
    return res

if __name__ == "__main__":
    n = int(input())
    cnt = 1
    stdNum = 1

    for j in range(1,n,2):
        cnt += factorial(n-stdNum) // (factorial(n-j-1) * factorial(stdNum))
        stdNum = stdNum + 1
    
        
    print(cnt)

DP 정답 풀이

dy라는 1차원 배열을 만들고,
1 2 3 4 5 6 7
□□□□□□□

• 1m 짜리를 자르는 방법은 1이다.(1m로만 가능하므로)
• 2m 짜리를 자르는 방법은 2이다. (1m,1m 가능 2m 가능)
• 3m 짜리를 자르는 방법은 나누어서 생각해보자.
  1 2 3 를 2m와 1m로 나누어보면
  □□□
  1 2----3 2m짜리를 구하는 방법은(1,1 & 2 +1 의 경우이다.)
  □□---□
  1 ---- 2 3 2m짜리를 구하는 방법은(1 + 1,1 & 2 의 경우이다.)
  □---□□

즉 구한것을 나열해보면
1+1+1
2+1
1+2 가 있는 것이다.
이 말은 뭐냐,

1 을 자르는 방법의 수와 2를 자르는 방법의 수를 더한 것이
3을 자르는 방법의 수가 된다.
1 2 3 4 5 6 7
①②□□□□□
3 = ③

예를 들어 4일 때
□□□+□ 상황에서는 끝이 1m 고정 이므로 앞에 3m를 자르는 경우의 수가 된다.
□□+□□ 상황에서는 끝이 2m 고정 이므로 앞에 2m를 자르는 경우의 수가 된다.
따라서 2+3 운 5가 되는 것이다.
이것이

dy[i] = dy[i-1] + dy[i-2]

import sys
sys.stdin = open("input.txt", "rt")

n = int(input())
dy = [0]*(n+1)
dy[1] = 1
dy[2] = 1

for i in range(3, n+1):
    dy[i] = dy[i-1] + dy[i-2]
print(dy[n])