코드트리 회전 마법진

 

문제 URL : https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-rotation-magic-circle/description

회전 마법진 설명 | 코드트리

문제 접근법 : 

문제를 잘못읽었다가 한참생각했네요

반시계 회전할때 모든 시계가 전부 회전해야하는줄 알았는데

자세히 읽어보니 뒤에있는것들이 움직인다고하니

해당 인덱스 에서 뒤까지만 움직이게 표현하면됩니다.

 

그렇다면 뒤에있는것들을 한번에 어떻게 회전시킬까요? 그것 우선 움직일려고 하지말고

뒤에 움직일때 반시계회전을 얼마나해줬는지 값만 전달해주면됩니다. 그리고 0~9까지가 주기니까 10으로 나눈 나머지가 계속 반복된다는것을 잊지만 않으면되요

소스코드:

 

 

#include <bits/stdc++.h>
using namespace std;

int n;

vector<int> v1,v2;
vector<vector<int>> dp;
string s1,s2;
int dfs(int cur=0,int r=0){
    if(cur>=n)return 0;
    int &cache = dp[cur][r];
    if(cache!=-1)return cache;
    int num = (v1[cur]+r)%10;
    //반시계방향 회전
    int pl = (v2[cur]-num+10)%10;
    //뒤에있는것까지  반시계 회전시키기
    int op1 = dfs(cur+1,(r+pl)%10)+pl;
    //해당것만 시계 회전
    int mi = (num-v2[cur]+10)%10;
    int op2 = dfs(cur+1,r)+mi;
    return cache = min(op1,op2);
}
int main() {
    cin>>n;
    cin>>s1>>s2;
    v1=v2=vector<int>(n);
    dp = vector<vector<int>>(n,vector<int>(10,-1));
    for(int i=0;i<n;i++){
        v1[i]=s1[i]-'0';
        v2[i]=s2[i]-'0';
    }
    cout<<dfs()<<"\n";
}

 

 

 

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