Level 2. 조이스틱

Level 2. 조이스틱

 

 

좌우로 조이스틱을 조작할 때 더 짧은 거리를 거리를 구하는 함수와 상하로 조이스틱을 조작할 때의 더 적은 비용을 구하는 함수를 만들었다.

• 인덱스 계산이 좀 번거롭긴 했다.

 

그리디로 풀었더니 오답처리 되었다.

 

// 이 풀이는 틀린 풀이다.
#include <iostream>
#include <cmath>

using namespace std;

int horizontal(int pos, string& current, string& name)
{
    int l = 0, r = 0;
    size_t len = name.length();

    while (current[(pos + l + len) % len] == name[(pos + l + len) % len])
        if (len <= -(--l))
            return len;

    while (current[(pos + r) % len] == name[(pos + r) % len])
        ++r;

    return (-l <= r) ? l : r;
}

int vertical(char c)
{
    return (c <= 'N') ? ('A' - c) : ('Z' + 1 - c);
}

int solution(string name)
{
    int answer = 0;
    int pos = 0, dist;
    int len = name.length();
    string current(len, 'A');

    while ((dist = horizontal(pos, current, name)) < len)
    {
        answer += abs(dist);
        pos = (pos + dist + len) % len;

        answer += abs(vertical(name[pos]));
        current[pos] = name[pos];
    }

    return answer;
}

 

그리디 문제인 줄 알았는데 아니었다.

 

매번 조이스틱을 움직일 때마다 왼쪽과 오른쪽으로 가는 비용을 재귀적으로 계산해 최솟값을 구해야 했다.

 

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

int horizontal(int pos, bool bLeft, string& current, string& name)
{
    int dist = 0;
    int d = (bLeft) ? -1 : +1;
    size_t len = name.length();

    while (current[(pos + dist + len) % len] == name[(pos + dist + len) % len])
        if (len <= abs(dist += d))
            return len;

    return dist;
}

int vertical(char c)
{
    return (c <= 'N') ? ('A' - c) : ('Z' + 1 - c);
}

int rDFS(int cost, int pos, string current, string& name)
{
    size_t len = name.length();
    int lDist = horizontal(pos, true, current, name);

    if (len <= abs(lDist))
        return cost;

    int rDist = horizontal(pos, false, current, name);

    string lCurrent(current);
    string rCurrent(current);

    int lPos = (pos + lDist + len) % len;
    int rPos = (pos + rDist) % len;

    int lCost = cost + abs(lDist);
    int rCost = cost + abs(rDist);

    lCurrent[lPos] = name[lPos];
    rCurrent[rPos] = name[rPos];

    lCost += abs(vertical(name[lPos]));
    rCost += abs(vertical(name[rPos]));

    return min(rDFS(lCost, lPos, lCurrent, name), rDFS(rCost, rPos, rCurrent, name));
}

int solution(string name)
{
    return rDFS(0, 0, string(name.length(), 'A'), name);
}