조이스틱 42860

문제

첫 번째 접근 방법

경우는 왼쪽, 오른쪽, 왼쪽으로 가다가 A를 만나 오른쪽,
오른쪽으로 가다가 A를 만나 왼쪽
이렇게 4개의 경우라고 생각했다.

첫 번째 실패

#include <string>
#include <vector>
#include <queue>

using namespace std;
struct wO
{
    string word;
    int dir;
    int idx;
    int val;
    bool isTurn;
};

int alphaNum(char c)
{
    return (c - 'A') > (c - 'A' - 26) * -1 ? (c - 'A' - 26) * -1 : (c - 'A');
}
int solution(string name)
{
    int minRet = 1000000, minVal = 0;

    queue<wO> wQ;
    string word = "";
    for (int i = 0; i < name.length(); ++i)
        word += 'A';
    wQ.push({word, 1, 0, 0, false});
    wQ.push({word, -1, 0, 0, false});
    while (!wQ.empty())
    {
        wO w = wQ.front();
        wQ.pop();
        w.word[w.idx] = name[w.idx];
        w.val += alphaNum(name[w.idx]);
        if (w.word == name)
        {
            if (minRet > w.val)
            {
                minRet = w.val;
            }
        }
        else
        {
            int idx = (w.idx + w.dir + name.length()) % name.length();
            if (!w.isTurn && (name[idx] == 'A'))
            {
                w.isTurn = true;
                wQ.push({w.word, -w.dir, w.idx, w.val, w.isTurn});
            }
            ++w.val;
            w.idx = idx;
            wQ.push({w});
        }
    }
    return minRet;
}

다른 방법을 생각해봐야겠다.

두 번째 접근 방법

무조건 A면 돌아가는 게 아니라 돌아가는 게 더 싼 값인지 확인하며 가면 될 것 같다.

코드

#include <string>
#include <vector>

using namespace std;

int alphaNum(char c)
{
    return (c - 'A') > (c - 'A' - 26) * -1 ? (c - 'A' - 26) * -1 : (c - 'A');
}
int solution(string name)
{
    int answer = 0;
    for (char c : name)
        answer += alphaNum(c);
    int minVal = name.length() - 1; // 오른쪽으로 이동할 값
    for (int i = 0; i < name.length(); ++i)
    {
        int nextI = i + 1;
        while (nextI < name.length() && name[nextI] == 'A')
            ++nextI;
        int right = name.length() - nextI;
        int minLR = i > right ? right : i;
        minVal = minVal > minLR + i + right ? minLR + i + right : minVal;
    }
    return answer + minVal;
}

풀이

알파벳을 변경하는 값은 변하지 않는다는 점을 이용하면 거리만 따로 계산해주면 된다.
돌아간다는 생각만을 계속해서 그런지 i를 2배해서 해결하려 했는데 오른쪽에서 돌아가는 경우도 있기에 계속 잘못된 답을 내놓았던 것 같다. 왼쪽과 오른쪽 중 더 작게 돌아가는 곳을 고르고 왼쪽과 오른쪽의 값을 더하면 해결된다.

왼쪽 A영역 오른쪽

이해하기 쉽게 설명하자면 A의 영역이 20이고 왼쪽, 오른쪽이 1이라면 왼쪽, 오른쪽만 접하면 될 것이다.
만약 A의 영역이 1이고 왼쪽, 오른쪽이 20이라면 돌아가는 비용이 더 크므로 쭉 가는 것이 더 작은 값일 것이다.
만약 왼쪽, A의 영역이 1이고 오른쪽이 20이라면 왼쪽부터 해결하고 오른쪽으로 가는 것이 더 작은 값일 것이다.
반대의 경우(왼쪽 20, A 1, 오른쪽 1)에는 오른쪽이 더 작을 것이므로 오른쪽부터 해결하고 돌아오는 것이 더 작은 값일 것이다.