프로그래머스 조이스틱

탐욕법 문제이지만 반례처리가 어려워서 다른 방법으로 했다. '한 번 방문한 인덱스'를 다시 방문하는 것은 최적 대상이 아닌 줄 알았지만 다음 반례가 존재했다

 

ABAAAAAAABA: 6

 

두번째 B를 처리하고 나서 왼쪽으로 이동하면서 최소로 수정할 수 있다. 따라서 처리과정이 모호해 bfs로 접근방식을 달리했다. 문자열이 짧다는 점에서 보다 빠르게 처리가 가능하다는 점을 이용했다

 

문제: https://programmers.co.kr/learn/courses/30/lessons/42860

깃허브주소: https://github.com/surinoel/boj/blob/master/Programmers_조이스틱.cpp

 

	#include <queue>
	#include <string>
	#include <vector>
	using namespace std;
	struct tp {
	int idx;
	int sum;
	string s;
	tp(int idx = 0, int sum = 0, string s = "") :
	idx(idx), sum(sum), s(s) {
	}
	};
	int ap[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
	bool check[21];
	int solution(string name) {
	int answer = 0;
	int len = name.size();
	queue<tp> q;
	q.push(tp(0, 0, name));
	while (!q.empty()) {
	tp t = q.front();
	q.pop();
	int idx = t.idx;
	int sum = t.sum;
	string s = t.s;
	bool ok = true;
	for (int i = 0; i < s.size(); i++) {
	if (s[i] != 'A') ok = false;
	}
	if (ok) {
	answer = sum - 1;
	if(answer == -1) answer = 0;
	break;
	}
	int tsum = 0;
	tsum += ap[s[idx] - 'A'];
	string ts = s;
	ts[idx] = 'A';
	if (idx - 1 == -1) {
	q.push(tp(len - 1, sum + tsum + 1, ts));
	}
	else {
	q.push(tp(idx - 1, sum + tsum + 1, ts));
	}
	if (idx + 1 == len) {
	q.push(tp(0, sum + tsum + 1, ts));
	}
	else {
	q.push(tp(idx + 1, sum + tsum + 1, ts));
	}
	}
	return answer;
	}

view raw Programmers_조이스틱.cpp hosted with ❤ by GitHub