네트워크 선 자르기 [DP]

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

 

 

풀이 

(1) Bottom Up : 작은문제부터 큰 문제로 키워나간다

- 주어진 길이의 네트워크 선을 자르는 방법을 탐색한다.

- 길이가 1이라면 1가지, 길이가 2라면 1+1/2+0으로 2가지 => 이런 기본값들은 dy배열에 저장해놓고 시작한다.

- 길이가 3이라면 1+1+1, 2+1, 1+2 => 3가지 => dy[1]+dy[2]

- 점화식을 구하면 f(n)=f(n-2)+f(n-1)

#include <stdio.h>
#include <algorithm>
using namespace std;
int dy[50];
//DP1. 네트워크 선 자르기(Bottom-Up)
//작은 문제 > 큰 문제로 확대
int main(){
    int n;
    scanf("%d", &n);
    dy[1]=1; 
    dy[2]=2;
    for(int i=3;i<=n;i++){
        dy[i]=dy[i-2]+dy[i-1];
    }
    printf("%d\n", dy[n]);
    return 0;
}

 

(2) Top Down: 재귀함수를 이용해 큰문제에서 작은 문제로 뻗어나가며 해결한다.

- 메모이제이션: 배열 값이 0보다 크면 이미 값을 구했으므로 다시 값을 구할 필요가 없다 =>  return dy[n]을 해주면 된다.

- 메모이제이션을 하지 않으면 속도가 매우 느리기 때문에 주의

#include <stdio.h>
#include <algorithm>
using namespace std;
int dy[101];
int n;
//DP2. 네트워크 선 자르기(Top-Down)

int DFS(int n)
{
    if (dy[n] > 0)
        return dy[n];
    if (n == 1 || n == 2)
        return n;
    else
        return dy[n] = DFS(n - 2) + DFS(n - 1);
}

int main()
{
    scanf("%d", &n);
    printf("%d\n", DFS(n));
    return 0;
}