[ 백준-3663번 / BF / 그리디 ] 고득점 풀이

1. 문제

---

 

3663번: 고득점

문제

현수는 조이스틱을 이용해 지렁이를 미로에서 탈출시키는 게임을 하고 있다. 최고 점수를 얻은 경우에는 조이스틱을 이용해서 이름을 입력해야 한다. 이름을 입력하는 과정은 다음과 같다.

가장 처음에 화면에 나와있는 이름은 'A'로만 이루어져 있다. 또, 이름의 첫 글자가 선택되어 있다. 조이스틱을 앞으로 움직이면 선택된 글자가 알파벳 다음 글자로 바뀐다. 조이스틱을 뒤로 움직이면, 알파벳 이전 글자로 바뀐다. 'Z'의 다음 글자는 'A'이고, 'A'의 이전 글자는 'Z'이다.

조이스틱을 왼쪽으로 움직이면, 현재 선택한 글자의 왼쪽 글자를 선택하게 되고, 오른쪽으로 움직이면 오른쪽 글자를 선택하게 된다. 가장 왼쪽 글자가 선택되었을 때, 조이스틱을 왼쪽으로 움직이면 마지막 글자를 선택하게 되고, 마지막 글자를 선택했을 때, 오른쪽으로 움직이면 첫 글자를 선택하게 된다.

현수는 조이스틱을 최소로 움직여서 이름을 입력하려고 한다. 현수가 입력하려고 하는 이름이 주어졌을 때, 이름을 입력하기 위해서 조이스틱을 최소 몇 번 움직여야 하는지 구하는 프로그램을 작성하시오. 현수가 입력하려는 이름의 길이와 처음에 화면에 나타나있는 이름의 길이는 같으며, 마지막에 선택하고 있는 글자는 중요하지 않다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 100이다.

각 테스트 케이스는 현수가 입력하려고 하는 이름이 주어진다. 이름의 길이는 최대 1000이며, 알파벳 대문자로만 이루어져 있다.

출력

각 테스트 케이스 마다, 조이스틱을 최소 몇 번 움직이면 이름을 입력할 수 있는지 출력한다.

예제 입력 1 복사

2 JEROEN JAN

예제 출력 1 복사

56 23

 

 

2. 소스코드

---

1회차 - 2020/06/25

 

- 백준에선 그리디 알고리즘으로 분류되어 있는데, 그리디인지 잘 모르겠다. 브루트 포스에 가깝지 않나 생각.

- 어느 글자를 먼저 바꾸든, 글자를 바꾸는데 필요한 최소값은 언제나 동일하다. 

- A(아스키 60) Z(아스키 90)임을 이용한다. 한 글자를 바꾸는데 드는 최소 비용은 min ( 바꾸는 글자 - 'A' , 'Z' + 1 - 바꾸는 글자 ) 이다.

- 바꿀 글자들을 최소로 이동하는 게 문제 풀이의 핵심인데,  현 위치에서 바꿔야할 글자 중 가장 가까이에 있는 글자로 이동하는 방법으로 그리디 알고리즘을 작성했다면 이는 최적해를 보장하지 않는다.

 

예를 들어,

- OAOAAAAAOAO 문자열을 최소로 바꾸려면,

 

AAAAAAAAOAO 맨 처음 위치를 바꾸고,

AAAAAAAAOAO 오른쪽으로 2칸

AAAAAAAAOAA 반대로 왼쪽으로 가면서 글자를 바꿔야 한다. 

AAAAAAAAAAA 총 7번 ( 오른쪽으로 2칸, 왼쪽으로 2칸, 왼쪽으로 3칸 )만에 모든 글자를 바꿀 수 있다.

 

- 위 방식이 아닌,

 첫 번째 글자에서 바꿔야할 글자 중 가장 가까운 위치로 이동하는 경우,

AAAAAAAAOAO

AAOAAAAAOAA 왼쪽 1칸

AAOAAAAAAAA 왼쪽 2칸

AAAAAAAAAAA 오른쪽 5칸

총 8칸으로 최적해가 아니다.

 

- 따라서 다른 방법을 사용해야하는데, 0(최초 시작점)을 기준으로 두 점을 잡고, 최소 이동거리를 계산했다.

- 글자를 아래와 같이 원으로 그려보면, 쉽게 이해할 수 있을 것 같다.

 

 

 

소스코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string str;

int main() {
	int T;
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> str;
		int answer = 0;
		int pos = 2e9;
		int size = str.size();
		for (int i = 0; i < size; i++)
			answer += min(str[i] - 'A', 'Z' - str[i] + 1);

		for (int i = 0, j; i < size; i++) {
			for (j = i + 1; j < size && str[j] == 'A'; j++);
			if (str[i] == 'A' && j == size + 1) break;
			int right = i * 2 + size - j;
			int left = i + (size - j) * 2;
			int temp = min(left, right);
			pos = min(temp, pos);
		}
		cout << answer + pos << "\n";
	}
}