프로그래머스 Level2_ 조이스틱 (C++)

분류는 그리디라고 되어있는데 최적의 해를 찾기 위해선 브루트포스 방식으로 코드를 짜야하는듯하다.

그리고 백준에도 같은 문제가 있는데 테스트케이스 조건이 더 빡빡해서 이 코드 그대로 썼다가 시간초과가 나서 백준에서는 코드를 수정하여 제출 했다.

백준 문제 : www.acmicpc.net/problem/3663

3663번: 고득점

#include <string>   // Level2_ 조이스틱 [그리디]
#include <vector>
#include <string.h>

#include <iostream>
#define calc(c) c - 'A' < 'Z' - c + 1 ? c - 'A' : 'Z' - c +1
using namespace std;

int right(int n, int start, string name, string target){
    int r = 0;
    if(name == target) {
        return 0;
    }
    if(n == target.length()) {
        n = 0;
    }

    name[n] = target[n];
    r += calc(target[n]); 
    r += right(n+1, start, name, target) + 1;
    return r;
}

int left(int n, int start, string name, string target){
    int r = 0;
    if(name == target) {
        return 0;
    }
    if(n < 0) {
        n = target.length()-1;
    };

    name[n] = target[n];
    r += calc(target[n]);
    r += left(n-1, start, name, target) +1;
    return r;
}

int solution(string name) {
    int answer = 10000000;

    for(int i=0; i<name.length(); i++){
        char s[21] = "AAAAAAAAAAAAAAAAAAAA";
        s[name.length()] = '\0';

        int n = calc(name[i]);
        s[i] = name[i];
        n += left(i-1, i, s, name) < right(i+1, i, s, name) ? left(i-1, i, s, name) : right(i+1, i, s, name);
        n += i;
        if (answer > n) answer = n;
    }

    return answer;
}