|
| 1 | +## 문제) |
| 2 | +동적계획법이란? 네트워크 선 자르기(Bottom-Up) |
| 3 | +현수는 네트워크 선을 1m, 2m의 길이를 갖는 선으로 자르려고 합니다. |
| 4 | +예를 들어 4m의 네트워크 선이 주어진다면 |
| 5 | + |
| 6 | +(1) 1m+1m+1m+1m\ |
| 7 | +(2) 2m+1m+1m\ |
| 8 | +(3) 1m+2m+1m\ |
| 9 | +(4) 1m+1m+2m\ |
| 10 | +(5) 2m+2m\ |
| 11 | + |
| 12 | +의 5가지 방법을 생각할 수 있습니다. (2)와 (3)과 (4)의 경우 왼쪽을 기준으로 자르는 위치가 |
| 13 | +다르면 다른 경우로 생각한다. |
| 14 | +그렇다면 네트워크 선의 길이가 Nm라면 몇 가지의 자르는 방법을 생각할 수 있나요? |
| 15 | + |
| 16 | +### 입력 설명 |
| 17 | +첫째 줄은 네트워크 선의 총 길이인 자연수 N(3≤N≤45)이 주어집니다. |
| 18 | + |
| 19 | +### 출력 설명 |
| 20 | +첫 번째 줄에 부분증가수열의 최대 길이를 출력한다. |
| 21 | + |
| 22 | +### 입력 예제 |
| 23 | +7 |
| 24 | + |
| 25 | +### 출력 예제 |
| 26 | +21 |
| 27 | + |
| 28 | +### 모범 답안 |
| 29 | +``` Cpp |
| 30 | +#include <iostream> |
| 31 | +#include <fstream> |
| 32 | +using namespace std; |
| 33 | +int dy[50]; |
| 34 | +int main() { |
| 35 | + ios_base::sync_with_stdio(false); |
| 36 | + ifstream cin; |
| 37 | + cin.open("input.txt"); |
| 38 | + |
| 39 | + int n; |
| 40 | + cin >> n; |
| 41 | + dy[1] = 1; |
| 42 | + dy[2] = 2; |
| 43 | + for (int i = 3; i <= n; i++) { |
| 44 | + dy[i] = dy[i - 1] + dy[i - 2]; |
| 45 | + } |
| 46 | + |
| 47 | + cout << dy[n]; |
| 48 | + |
| 49 | + return 0; |
| 50 | +} |
| 51 | +``` |
| 52 | + |
| 53 | +### 동적계획법이란? |
| 54 | +너무 복잡하고 어려워서 한번에 풀 수 없을 때\ |
| 55 | +아주 작은 단위의 문제로 쪼갠 다음 풀이 후 기록하고\ |
| 56 | +앞서 구한 작은 단위의 문제 풀이를 활용해서\ |
| 57 | +조금 더 큰 문제를 풀고 기록하는 방식을 지속해서\ |
| 58 | +결국 처음 당면한 크고 복잡한 문제를 풀어나가는 방식을 \ |
| 59 | +동적계획법이라고 한다. |
| 60 | + |
| 61 | +### 문제 풀이 접근법 |
| 62 | +1. dy[1] = 1 -> 길이가 1일 때 나눌 수 있는 방법의 수({1}) |
| 63 | +2. dy[2] = 2 -> 길이가 2일 때 나눌 수 있는 방법의 수({1,1}, {2}) |
| 64 | +3. dy[3] = dy[2] + dy[1] |
| 65 | + - 마지막 짜르는 지점이 1일 때([][]/[]) |
| 66 | + - 길이가 2일 때 나눌 수 있는 방법의 수 |
| 67 | + - 마지막 짜르는 지점이 2일 때([]/[][]) |
| 68 | + - 길이가 1일 때 나눌 수 있는 방법의 수 |
| 69 | +4. dy[4] = dy[3] + dy[2] |
| 70 | + - 마지막 짜르는 지점이 1일 때([][][]/[]) |
| 71 | + - 길이가 3일 때 나눌 수 있는 방법의 수 |
| 72 | + - 마지막 짜르는 지점이 2일 때([][]/[][]) |
| 73 | + - 길이가 2일 때 나눌 수 있는 방법의 수 |
| 74 | + - 1과 2로만 짤라야하기 때문에 뒤에서 최대로 짜를 수 있는 갯수는 2이다. |
| 75 | + |
| 76 | +결국 f(n) = f(n-1) + f(n-2)라는 식을 도출 할 수 있다. |
0 commit comments