Greedy
조이 스틱
풀이과정
알파벳 위 아래로 조작하는 건 알겠고, 단순히 오른쪽으로 쭉 이동하거나 왼쪽에서 쭉 이동하는 것만 비교해서 제출했더니 11번 테케에서 오류나서 구글링의 힘을 빌렸다..
간단한 건데도 이해하기 힘들어서 직접 써서 증명하면서 풀었다 ㅠㅠ 그리디 넘 어려웡
- name[i]에서 가장 가까운 A가 아닌 문자 name[ind] 찾기
- 여기서 조이스틱을 움직이는 최단 경로는
(1) 원점 –> i –> 원점 –> ind
(2) 원점 –> ind –> 원점 –> i
이렇게 두 가지이다. - 따라서
(i : 0~name.length)에 대해 조이스틱을 움직이는 최소값을 구한다.
반례인 “ABABAAAAABA”에 대해 위 풀이를 수식으로 설명해보면 다음과같다.
코드
#include <algorithm>
#include <string>
using namespace std;
int solution(string name) {
int answer = 0;
int n = name.length();
int turn = n - 1; //조이스틱을 한 방향으로 쭉 움직였을 때
for (int i = 0; i < n; i++) {
if (name[i] - 'A' < 14) answer += name[i] - 'A';
else answer += 'Z' - name[i] + 1;
int ind = i + 1;
while (ind < n && name[ind] == 'A') ind++;
turn = min(turn, i + n - ind + min(i, n - ind));
}
answer += turn;
return answer;
}
REFERENCE
[프로그래머스] 조이스틱