Programers:Joycastic(greedy)


木の棒



コード#コード#

#include <string>
#include <vector>

using namespace std;

int solution(string name) {
    int answer = 0,i=0;
    string str ="";
    /* str 초기화 */
    for(int i=0;i<name.length();i++) str+="A";
    while(name != str)
    {
        char ch = name[i];
        /* 조이스틱을 올릴지, 내릴지에 대해 최소값으로 빼기! */
        int dif = min(ch-'A', 'Z'-ch+1);
        answer += dif;
        /* 바꾸어야 할 값을 A로 치환 --> 밑에서 A가 아닌 요소로 값을 찾기 때문! */
        name[i] = 'A';
        if(name == str) break;
        /* 앞으로 갈지, 뒤로 갈지 정함! --> A가 아닌 요소가 먼저 나오면 break! */
        for(int k=1;k<=name.length()/2;k++){
            int prev_idx = i-k < 0 ? i-k+name.length() : i-k;
            int next_idx = i+k > name.length()-1 ? i=i+k-name.length() : i+k;
            if(name[next_idx] != 'A') {
                i = next_idx;
                answer += k;
                break;
            }
            else if(name[prev_idx] != 'A'){
                i = prev_idx;
                answer += k;
                break;
            }
        }
    }
    return answer;
}
  • key point!
    1)minで上下移動レバーの選択を解決する
    2)レバーを左/右に動かす場合は、まず「A」以外の要素を探し、次に
    -->名前を変更した値を「A」に変換する必要があります.