[백준][1796번][DP] 신기한 키보드

신기한 키보드

https://www.acmicpc.net/problem/1796

<내가 푼 코드>

#include <stdio.h>
 
int max(int a, int b){ return a > b ? a : b; }
int min(int a, int b){ return a > b ? b : a; }
int abs(int a){ return a > 0 ? a : -a; }
 
char lcdS[1001];
int totalmove = 10000000;
int alpaindex[26][2];
 
///////////////////////////////////////////////////////////////////////////////////
//
//        재귀를 통해서 완전 탐색을 한다
//    
//        입력 : 문자열 크기 , 지금 알파벳 , 현재 커서의 위치 , 지금까지 누른 타자 수
//
////////////////////////////////////////////////////////////////////////////////////
 
 
void allsimulate(int size, int alpa, int preCusur , int totalcount){
 
    int maxindex = -1, minindex = 1100;
 
    if (totalcount > totalmove)
        return;
    if (alpa > 'z')
    {
        if (totalcount < totalmove)
        {
            totalmove = totalcount;
        }
        return;
    }
 
    maxindex = alpaindex[alpa - 'a'][0];
    minindex = alpaindex[alpa - 'a'][1];
 
    // 한 문자에 대해서 양 끝에 있는 것만 알면 됩니다.
 
    // 문자가 하나만 있을때
    if (maxindex == minindex){    
        allsimulate(size, alpa + 1, maxindex, totalcount + abs(preCusur - minindex) + abs(maxindex - minindex));
    }
    // 문자가 두개 이상 있을 때
    else if (maxindex != -1){
        allsimulate(size, alpa + 1, maxindex, totalcount + abs(preCusur - minindex) + abs(maxindex - minindex));
        allsimulate(size, alpa + 1, minindex, totalcount + abs(preCusur - maxindex) + abs(maxindex - minindex));
    }
    // 문자가 없을 때
    else{
        allsimulate(size, alpa + 1, preCusur, totalcount);
    }
}
 
int main(void){
 
 
    int size = 0;
    int preCusur = 0;
 
    // 문자열 입력을 받는다.
    scanf("%s", lcdS);
    while (lcdS[size] != 0)
        size++;
 
    // 각 문자에 대해서 양 끝에 대한 값을 찾아서 집어넣어준다.
    for (int alpah = 'a'; alpah <= 'z'; alpah++){
        int maxindex = -1, minindex = 1100;
        for (int i = 0; i < size; i++){
            if (lcdS[i] == alpah)
            {
                maxindex = max(i, maxindex);
                minindex = min(i, minindex);
            }
        }
        alpaindex[alpah - 'a'][0] = maxindex;
        alpaindex[alpah - 'a'][1] = minindex;
 
    }
 
    // 재귀 이용
    allsimulate(size, 'a', preCusur, 0);
    //엔터 입력 추가
    totalmove += size;
    
    printf("%d\n", totalmove);
    
 
    return 0;
}

< 문제 푼 방법>

 1. 조건 엔터를 치는 경우는 생각을 안해도 된다 왜냐하면 n개 이기 때문이다.

 2. 같은 문자에서는 가장 양 끝의 것만 신경 써주면 된다.

 3. 현재의 커서를 알고 다음 알파벳의 양 끝의 index 값을 가지고 계산해준다. 

 4. 계산되어야 할 값은 같은 문자에서 양 끝의 이동 거리 그리고 다음 알파벳 양 끝으로가는 이동거리이다. 

 5. 그래서 이 경우의 수를 완전탐색 하는데 이 것을 재귀로 풀었다

     (1) 재귀의 탈출 조건 

- 이미 구해놓은 값보다 구하고 있는 값이 클 때 탈출 (왜냐하면 우리는 최소값만 알면 된다.)

- a~ z 까지 모든 탐색을 끝내면 그 값을 저장하고 탈출한다.

     (2) 재귀의 불러올 조건 

- 알파벳이 1개만 존재할 때

- 알파벳이 2개 이상 존재할 때

- 알파벳이 존재하지 않을 때

6. 재귀가 끝난다면 최소값이 구해진것을 볼 수 있다.

7. 다른 문제 풀이 방법으로는 DP로 푸는 방식이 있다고 한다.