경작 12일차 DP

#230209 목

알고리즘 스터디에서 DP 문제를 풀었다. 오늘의 후기 : 난 사실 DP를 모르는 거 아닐까? 알고 있는데 이렇게 못 풀 수가 있다고? 진짜 amazing my life

1. 백준 2747번 피보나치 수

피보나치 수 문제는 n번째 피보나치 수를 구하기 위해서 n-1과 n-2의 피보나치 수를 먼저 구하므로, 작은 문제(n-1 피보나치 수, n-2 피보나치 수 구하기)의 결과값들을 모아 큰 문제(n번째 구하기)의 결과값을 구하는 DP라고 할 수 있다.

사실 이건 너무 쉬워서 5분밖에 안 걸렸다. 다른 문제도 다 이런 식이면 내 인생이 좀 행복할 텐데... ..가 아니라 이미 조기졸업하고 어디 좋은 직장으로 납치되지 않았을까

내 코드:

#include <iostream>
using namespace std;
int num;
int idx;
int result;

void function(int n1, int n2){
    if(idx>=num) result=n2;
    else{
        idx++;
        dpfunction(n2, n1+n2);
    }
}

int main(){
    cin>>num;

    idx=1;
    function(0,1);

    cout<<result;
}

2. 백준 14002번 가장 긴 증가하는 부분 수열 4

가장 긴 증가 수열 그냥 연결리스트 만들어서(자신의 오른쪽에 있는 수들 중 자신보다 큰 숫자들은 모두 자신과 연결) 푸는 방법은 알긴 하는데

그걸 c++한테 시켜본 건 아니고 내 손한테 시켜본 적은 있다 ㅋ

ㅋ
ㅋㅋ
c++아 대신 해줘~
(c++ : 니가 제대로 줘야 내가 풀 거 아냐)

---

<문제>
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

<입력>
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

<출력>
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.

---

왜 비스에선 잘만 되는데 백준에서는 틀렸다고 할까...
모르겠다.. 나 이거 너무 오래 풀어서 걍 모르는 채로 살란다 힘들어

내 (틀린) 코드 :

#include <iostream>
#include <vector>
using namespace std;
int num;
int inputarray[1001];
vector<int> adj[1001];
int lengtharray[1001];
int previous[1001];
int maxlength=0;
int tmplength;

int main(){
    cin>>num;
    
    for(int i=0;i<num;i++){
        cin>>inputarray[i];
    }
    
    for(int i=0;i<num;i++){
        for(int j=i+1;j<num;j++){
            if(inputarray[i] < inputarray[j]){
                adj[j].push_back(i);
            }
        }
    }
    
    for(int i=0;i<=1001;i++){
        lengtharray[i] = 1;
        previous[i] = -1;
    }
    
    int maxidx;
    
    for(int k=1;k<=num;k++){
        if(adj[k].size()!=0) {
            tmplength = -1;
            for(int i=0;i<adj[k].size();i++){
                int tmp = adj[k][i];
                if(lengtharray[tmp] > tmplength){
                    tmplength = lengtharray[tmp];
                    previous[k] = tmp;
                }
            }
            lengtharray[k] = tmplength+1;
            if(lengtharray[k] > maxlength){
                maxlength = lengtharray[k];
                maxidx = k;
            }
        }
    }
    
    cout<<maxlength<<'\n';
    vector<int> resultarray;
    
    resultarray.push_back(maxidx);
    
    while(previous[maxidx] != -1){
        resultarray.push_back(previous[maxidx]);
        maxidx = previous[maxidx];
    }
    
    for(int i=0;i<resultarray.size();i++){
        for(int j=i+1;j<resultarray.size();j++){
            if(resultarray[i] > resultarray[j]){
                int tmp2 = resultarray[i];
                resultarray[i] = resultarray[j];
                resultarray[j] = tmp2; 
                
            }
        }
    }
    
    for(int i=0;i<resultarray.size();i++){
        cout<<inputarray[resultarray[i]]<<' ';
    }
}