Softeer 조립라인 (c++)

문제 URL : https://www.softeer.ai/practice/6287

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

문제 접근법:  dp 문제입니다.

dfs를 이용해서 메모이제이션으로 해결한문제이고

문제는 간단합니다.  min(현재 일처리후 바로 다음라인에서 처리하는 값과 ,  현재일처리후 다른 작업장에있는 다음라인 처리하는값 + 거기까지 이동하는 시간) 을 계산해서

메모이제이션으로 빠르게 풀수있는문제 입니다.

 

소스코드 : 

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n;
vector<ll> v[2],m[2],dp[2];
void input(){
    cin>>n;
    v[0]=v[1]=m[0]=m[1]=vector<ll>(n);
    for(int i =0;i<n-1;i++){
        cin>>v[0][i]>>v[1][i]>>m[0][i]>>m[1][i];
    }
    cin>>v[0][n-1]>>v[1][n-1];
}
ll dfs(int cur,int pos){
    if(cur>=n)return 0;
    ll &cache =dp[pos][cur];
    if(cache !=1e9)return cache;
    return cache = min(dfs(cur+1,pos)+v[pos][cur],dfs(cur+1,!pos)+v[pos][cur]+m[pos][cur]);
}
void solve(){
    dp[0]=dp[1]=vector<ll>(n,1e9);
    cout<<min(dfs(0,1),dfs(0,0))<<"\n";

}
int main(){
    
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    input();
    solve();
    
}

 

 

궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.