lv2 조이스틱

일단 알파벳을 바꾸는 횟수는 무엇을 해도 같다.

즉 AAAAAA => JEROEN 를 바꿀때는

J-A = 9 

E-A = 4

R-A = 9

O-A = 12

E-A = 4

N-A = 13

13+21+17 = 51번은 뭘 어떻게 해도 들어간다.

 

이제 구해야 할것은 조이스틱의 <- 방향과 -> 방향만을 신경써서 어떻게 움직일까이다.

 

첫 생각은 이렇게 했다.

 

예를들면 

A B B B A A A B B B A A 문자열에서 0번 커서 기준으로

0 1 2 3 4  5 6  7 8 9 10 11

조이스틱을 오른쪽으로만 갈때 A가 아닌 문자열의 최대값 = 9

즉 -> 방향을 9번만 쓰면 된다.

왼쪽으로만 갈때 A가 아닌 문자열의 최소값(0번째 빼고) = 1 

즉 <- 방향을 12-1= 11번만 쓰면 된다.

 

JEROEN 은 

-> == 5

<- == 5 니

51+5 == 56 이 나왔지만 틀렸다.

 

 

이유가 무엇이였을까?

 

반례는 ABABABAAAAAAAAAAAAAAAAAAABA 였다.

직접 손으로 해보면 이것의 <- -> 방향은 12번만 쓰면 된다. 

하지만 저 위에 내 생각으로 하면 답은 25이다.

 

오른쪽만 , 왼쪽만 가는게 아니라 오른쪽으로 갔다가 왼쪽으로 꺾을 수 있다는 것이다.

 

 

그러면 어떻게 했냐?

A 가 아닌것을의 위치를 구한다.  ABABABAAAAAAAAAAAAAAAAAAABA 기준

1 3 5 25이다.

 

일단 초기값은 min(그냥 -> 만 했을때, 그냥 <- 만 했을때) = 25.

 

1, 3 기준 0->1 갔다가(1) 1->0-> 26->25->24......->3 까지 간 거리를 구한다.(25) => 26

3 5 기준 0->1->2->3 갔다가 3->2->1->0->26.... ->5 까지 간 거리를 구한다. => 3 +25 = 28;

5 25 기준 0->1->2->3->4->5 갔다가 5->4->3->.. 0->26->25 까지 간 거리를 구한다. => 12;

최소 이동거리는 12

 

 

 

 

 

 

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define pii pair<int, int>
using namespace std;
 
int make(int n)
{
    cout << min(n - 1, 27 - n) << ' ';
    return min(n - 1, 27 - n);
}
 
 
int solution(string s)
{
    int ans = 0;
    vector<int> pos;
    for (int i = 0; i < s.size(); i++)
    {
        ans += make(s[i] - 'A'+1);
        if (s[i] != 'A')
            pos.push_back(i);
    }
 
    int minn = min(pos[pos.size() - 1], (int) s.size() - pos[0]);
 
    for (int i = 0; i < pos.size() - 1; i++)
    {
        minn = min(minn, pos[i] + (pos[i] + (int)s.size()) - pos[i + 1]);
    }
 
    return ans + minn;
 
}