[백준] 9486 이름 남기기 - C++

 

 

 

N이 적당히 작으니 비트필드를 사용할 수 있다.

 

dp[status][cur] = 현재 입력을 완료한 상태는 status이고 지금은 cur번째 문자를 입력하고 있을 때의 최소 클릭 횟수

위와 같이 dp 배열을 정의하자.

 

재귀함수는 두 가지 케이스로 나뉜다.

 

1. 아무것도 입력하지 않은 경우

2. 뭔가 입력된 상태

 

아무것도 입력하지 않은 경우 문자는 A부터 시작하고, 어떤 문자부터 입력해야 최소 횟수를 반환하는지 알 수 없으니 모든 경우를 살펴봐야 한다.

 

뭔가 입력된 상태에서는 왼쪽 혹은 오른쪽으로 이동하는 경우도 추가로 생각해 줘야 하고, 이전에 입력한 문자부터 시작되는 부분을 고려해야 한다.

 

최소 횟수를 구하는 문제이니 INF를 적당히 설정해 주자.

 

 

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <memory.h>
#include <cmath>

using namespace std;
typedef long long ll;
const int INF = 987654321;

string str;
int dp[1<<19][19];
int N;

int calc(int num) {
	if(num >= 13) num = 26 - num;
	return num;
}

int solve(int status, int cur) {
	if(status == (1<<N) - 1) return 0;

	int& ret = dp[status][cur];
	if(ret != -1) return ret;
	
	ret = INF;

	if(status == 0) {
		for(int i=0; i<N; i++) {
			int cnt = calc(str[i] - 'A');
			ret = min(ret, solve(1 << i, i) + 1 + cnt);
		}
	} else {
		for(int i=0; i<N; i++) {
			if((status & (1 << i)) != 0) continue;
			int cnt = abs(str[i] - str[cur]);
			cnt = calc(cnt);

			int move = 0;

			if(i < cur) {
				move++;
				for(int j=i+1; j<cur; j++) {
					if((status & (1 << j)) != 0) {
						move++;
					}
				}
			} else {
				for(int j=cur+1; j<i; j++) {
					if((status & (1 << j)) != 0) {
						move++;
					}
				}
			}

			ret = min(ret, solve(status | (1 << i), i) + cnt + 1 + move);

		}
	}	

	return ret;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);

	while(1) {
		cin >> str;		
		N = str.size();
		if(str[0] == '0') break;
		memset(dp, -1, sizeof(dp));		
		cout << solve(0, 0) << endl;
	}	
}