반례

• 복귀를 해야 하고,
• 나를 대상으로 뒤에 오는 value 중에 'a'가 아닌 값을 대상으로 확인하는 식으로 하면 이전에 오는 알파벳에 대해 생각할 필요 없다.
  -> 이미 완료된 상태다.

핵심!

• 빨간색 1번과 2번을 비교하고 있는데, b에 대해서는 생각할 필요가 없다.
• 나중에 2번을 가지고 다음 pos에 오는 거를 확인할 것이다. 굳이 필요 없다!
  

수식을 작성하면서 해보자..

-> 260327

---

최근 문제 풀이_260326 : 틀림

• 잘못된 풀이
  

• 반례가 있다.
  : 한쪽으로만 가능 코드로 하면 안된다. 이때는 유턴하는 것이 효율적이다.
  

결론 : 반례를 먼저 생각해보고 접근해야 한다.

• 나의 생각인 2번과 3번에 대한 반례를 생각하는 시간을 가져야 한다.
  
  

• 구글링.
  

그리디라고 판단되면?

• 내가 생각한 해결전략에서 반례에 대해서 작성하자.

---

풀이전략

• 풀다 보니 dp로 알파벳 a부터 z까지 타겟으로 잡은 값을 비교한 최소값을 넣어준 다음에 해야 효율이 좋겠구나 생각을 했지만, 이미 순차적으로 진행해서
  못 바꿈.

1. 자리 이동하는 거 cur위치에서 타겟 자리로 좌측이동 vs 우측 이동한 값의 최소값을 구하고,
2. 알파벳을 위로 이동 vs 아래로 이동 최소값을 구한다
3. 1번과 2번의 값을 더한 값을 dp값에 넣어주고.
4. 최종으로 다 더해주는 방법으로 진행했다.

// 반례

지금 내가 만든 반복문으로는 순차적으로 밖에 진행하지 못하지만,
반례를 보면 0번 인덱스 마치고, 마지막 인덱스로 이동해서 진행하는 것이
최소화 할 수 있다.
이 부분을 생각하지 못해서 만점아님..
추후에 다시 풀자...

소스코드

#include <string>
#include <vector>

using namespace std;

//0823 16:03 ~ 17:11
int solution(string name) {
    int answer = 0;
    
    int dp[20] = {0,};
   
    int curIndex = 0;
    
    for(int index = 0; index < name.length(); index++)
    {
        //타겟값이 a일때는 상관없다. 자리 이동값만 구하면됨
        //0번 인덱스에서 오른쪽으로 몇번째 위치해 있는지
       
        if(name[index] != 'A')
        {
            //알파벳 이동했을때의 최소값 - 2번
            int alphaA = 0; //a에서 뺏을 때.
            alphaA = name[index] - 'A';
            
            //z에서 뺏을때
            int alphaZ = 0;
            alphaZ = 'Z' - name[index] + 1;
            int upDown = 0;
            upDown = min(alphaA, alphaZ);       
            
            //자리 이동했을때의 최소값 - 2번
            int locStart = 0;      
            locStart = index - curIndex;
            
            //0번 인덱스에서 좌측으로 이동할때 몇번 이동하는지
            int locEnd = 0;
            //locEnd = name.length() - index;
            locEnd = name.length() - index + curIndex ;
            
            int leftRight = min(locStart, locEnd);
            
            dp[index] = upDown + leftRight;
            answer += dp[index];
            
            curIndex = index;
            
        }
       
            
             
        //answer = dp[index];
        //break;
        
        //최소값을 dp에 더하기 
            
    }
    
    
    return answer;
}