백준(BOJ) Implement ZOAC 3(20436) - Silver4

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

20436번: ZOAC 3

문제

2020년 12월, 세 번째로 개최된 ZOAC의 오프닝을 맡은 성우는 누구보다 빠르게 ZOAC를 알리려 한다.

하지만 안타깝게도 성우는 독수리타법이다!

• 독수리 타법이란 양 손의 검지손가락만을 이용해 타자를 치는 타법이다.
• 성우는 한글 자음 쪽 자판은 왼손 검지손가락으로 입력하고, 한글 모음 쪽 자판은 오른손 검지손가락으로 입력한다.
• a의 좌표가 (x1, y1)이고, b의 좌표가 (x2, y2)일 때, a에 위치한 성우의 손가락이 b로 이동하는 데에는 a와 b의 택시 거리 |x1-x2|+|y1-y2| 만큼의 시간이 걸린다.
• 각 키를 누르는 데에는 1의 시간이 걸린다.
• 성우는 두 손을 동시에 움직일 수 없다.
• 성우가 사용하는 키보드는 쿼티식 키보드이며, 아래 그림처럼 생겼다.

바쁜 성우를 위하여 해당 문자열을 출력하는 데 걸리는 시간의 최솟값을 구해보자.

입력

첫 번째 줄에는 두 알파벳 소문자 sL, sR이 주어진다. sL, sR은 각각 왼손 검지손가락, 오른손 검지손가락의 처음 위치이다.

그 다음 줄에는 알파벳 소문자로 구성된 문자열이 주어진다. 문자열의 길이는 최대 100자이다. 빈 문자열은 주어지지 않는다.

출력

입력으로 주어진 문자열을 출력하는 데에 걸리는 시간의 최솟값을 출력한다.

문제 해결

단순 구현 문제로 어려운 알고리즘은 들어가지 않는다. 메모리와 시간제한을 봤을 때 완전탐색으로도 해결할 수 있다고 생각했다. 문제는 총 3단계로 나눠서 처리할 수 있다.

1. 키보드 셋팅 -> 왼쪽 키보드와 오른쪽 키보드에 맞게 설정을 해준다. 이 때 주의해야 할 점은 오른쪽 키보드에 있는 'b'문자는 다른 문자보다 한 칸 들어가 있다는 점이다.

2. 들어온 문자가 왼손을 써야하는지 오른손을 써야하는지 찾는 find 함수 이 때 해당 좌표도 찾아줘야 함

3. 마지막으로 거리 계산해주는 함수 

 

전체코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#define N 3
#define M 5

using namespace std;

typedef long long ll;

vector<vector<char> >leftKey(N, vector<char>(M));
vector<vector<char> >rightKey(N, vector<char>(M+1));
pair<ll, ll>point;
pair<ll, ll>sl_point;
pair<ll, ll>sr_point;

void init(char left, char right){
    leftKey[0][0] = 'q'; leftKey[0][1] = 'w'; leftKey[0][2] = 'e';  leftKey[0][3] = 'r'; leftKey[0][4] = 't';
    leftKey[1][0] = 'a'; leftKey[1][1] = 's'; leftKey[1][2] = 'd';  leftKey[1][3] = 'f'; leftKey[1][4] = 'g';
    leftKey[2][0] = 'z'; leftKey[2][1] = 'x'; leftKey[2][2] = 'c';  leftKey[2][3] = 'v'; leftKey[2][4] = '0';

    rightKey[0][0] = '0'; rightKey[0][1] = 'y'; rightKey[0][2] = 'u'; rightKey[0][3] = 'i';  rightKey[0][4] = 'o'; rightKey[0][5] = 'p';
    rightKey[1][0] = '0'; rightKey[1][1] = 'h'; rightKey[1][2] = 'j'; rightKey[1][3] = 'k';  rightKey[1][4] = 'l'; rightKey[1][5] = '0'; 
    rightKey[2][0] = 'b'; rightKey[2][1] = 'n'; rightKey[2][2] = 'm';  rightKey[2][3] = '0'; rightKey[2][4] = '0'; rightKey[2][5] = '0'; 
    // 빈 자리는 '0'으로 대체 
    // 오른쪽 키보드 B는 살짝 들어와 있다...
    


    for(ll i=0; i<N; i++){
        for(ll j=0; j<M; j++){
            if(leftKey[i][j] != '0' && (leftKey[i][j] == left)){
                sl_point.first = i;
                sl_point.second = j;
            }
        }
    }
    for(ll i=0; i<N; i++){
        for(ll j=0; j<M+1; j++){
            if(rightKey[i][j] != '0' && (rightKey[i][j] == right)){
                sr_point.first = i;
                sr_point.second = j;
            }
        }
    }
}

void print(string key){
    if(key == "left"){
        for(ll i=0; i<N; i++){
            for(ll j=0; j<M; j++){
                if(leftKey[i][j] != '0')
                    cout << leftKey[i][j] << " ";
                }
                cout << "\n";
            }
    }   
    else{
        for(ll i=0; i<N; i++){
            for(ll j=0; j<M; j++){
                if(rightKey[i][j] != '0')
                    cout << rightKey[i][j] << " ";
            }
            cout << "\n";
        }
    }
}


ll findKey(char ch){
    for(ll i=0; i<N; i++){
        for(ll j=0; j<M; j++){
            if(leftKey[i][j] != '0' && (leftKey[i][j] == ch)){
                point.first = i;
                point.second = j;
                return 1;
            }
        }
    }
    // left 키보드에 위치 1
    for(ll i=0; i<N; i++){
        for(ll j=0; j<M+1; j++){
            if(rightKey[i][j] != '0' && (rightKey[i][j] == ch)){
                point.first = i;
                point.second = j;
                return 2;
            }
        }
    }
    return -1;
    // right 키보드에 위치 2
}


ll get_score(string key){
    ll distance = 0;
    if(key == "left"){
        distance = abs(sl_point.second - point.second) + abs(sl_point.first - point.first);
        sl_point = point;
    }
    else{
        distance = abs(sr_point.second - point.second) + abs(sr_point.first - point.first);
        sr_point = point;
    }
    return distance;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("input.txt", "r", stdin);

    char left, right;
    cin >> left >> right;
    string str;
    cin >> str;
    // ------- input --------

    init(left, right); 
    // step1. 키보드 Setting 


    // step2. find -> 완전탐색 input으로 들어간 문자가 키보드 어디에 위치했는지 좌표 저장 1은 왼쪽 키보드 2는 오른쪽 키보드
    // step3. get_score 시작 위치와 현재 문자의 위치를 계산
    ll answer = 0 ;
    for(ll i=0; i<str.size(); i++){
        if(findKey(str[i]) == 1) // 왼쪽 키보드
            answer += get_score("left");
        else // 오른쪽 키보드
            answer += get_score("right");
        answer++;
    }
    cout << answer << "\n";
    return 0;
}