코드트리 적절하게 숫자를 변경하

문제 URL : https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-change-number-properly/description

적절하게 숫자를 변경하기 설명 | 코드트리

 

문제 접근법 : 

모든 경우를 다 만들어 보는겁니다. 그중 유사도가 가장높은것을 선택하고

dp+메모이제이션 기법으로 가지치기만 해주면 풀수있는 문제입니다.

 

소스코드:

 

 

 

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int>v;
vector<vector<int>>dp[5];
int dfs(int num,int cur=0,int k=0){
    if(k>m)return -1e9;
    if(cur>=n)return 0;
    int &cache = dp[num][cur][k];
    if(cache!=-1)return cache;
    int res = (num==v[cur]);
    //5개의 값
    int score[5]={0};
    for(int i =1;i<=4;i++){
        score[i]=dfs(i,cur+1,k+(i!=num));
    }
    //그중 유사도가 가장높은것만 선택
    res+=max({score[1],score[2],score[3],score[4]});
    return cache = res;
}
int main() {
    cin>>n>>m;
    v= vector<int>(n);
    for(int i =0;i<=4;i++)dp[i]=vector<vector<int>>(n+1,vector<int>(m+1,-1));
    for(int i =0;i<n;i++){
        cin>>v[i];
    }

    //첫시작이 1,2,3,4
    cout<<max({dfs(1),dfs(2),dfs(3),dfs(4)});

}

 

 

 

궁금한점 혹은 모르는점 어떤 질문이든 댓글은

언제나 환영입니다.