[ C++ / 백준 ] 1796 신기한 키보드

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

1796번: 신기한 키보드

 
[...]
일단, 처음에 문제를 보면서 "타자 입력" "엔터나 오른쪽 왼쪽"을 보고 stack, bfs를 떠올렸다. 혹시 DP? 하기도 했는데 아니겠지하고 넘어감 ㅎㅎ..
 
그리고 문제를 풀면서 풀이 방법에 근접한 방법을 생각해 냈는데 난독 이슈로 이상한 방법으로 풀이를 하다가 집어 던졌다... stack + 오른쪽 왼쪽 막 구현 하고 그런 거엿음 ㅋㅋㅋ
나중에 분류 표랑,, 스터디원 분이 잘못 읽은거 알려주셔서 풀 수 있었다 ^.T
 
 
 
[문제 풀이]
일단, 문제에서 찾아야 할 규칙이 있다.
 
"한 문자를 전송하는 과정에서 다음 문자 단계로 넘어가기 전 커서의 위치는 무조건 가장 앞 혹은 뒤"
 
예시를 들어서 abcabbcab라는 문자열을 입력받았다고 하자. 
a의 위치 :  0,3,7
b의 위치 : 1,4,5,8
 
문제에 따르면 다음과 같은 과정을 거친다
 
1. 먼저, 'a'를 찾아서 전송한다

위 그림에서 보이듯이, a가 최소가 되기 위한 방향은 오른쪽으로 직진해서 마지막 위치한 'a'까지 가는 것이다.
마지막에 위치한 'a'까지 가는 동안 그 사이에 있는 'a'들도 모두 enter를 치고 넘어갈 것으로 예상된다.
 
2. 다음으로, 'b'를 찾아서 전송한다.

'b'도 마찬가지로 경로 상에 있는 'b'는 모두 전송할 수 있는 것이니까, 
1) 맨 오른쪽으로 갔다가 왼쪽으로 가거나
2) 왼쪽으로 갔다가 오른쪽으로 가거나
두 가지 경우로 나누어 진다.
 
그럼 우리가 기록할 수 있는건, 커서가 마지막으로 오른쪽에 위치하냐? 왼쪽에 위치하냐? 로 나눌 수 있는 것이다. 
그래서 이걸 DP로 표현할 수가 있다. 
 
예시를 좀 바꿔서 
abcdbbcdb라고 하자. 
a: 0
b: 1, 4, 8
c: 2, 6
 
그리고 DP[][0] : 해당 문자를 전송했을 때, 커서가 맨 앞 문자 위치에 있을 경우
DP[][1] : 커서가 맨 뒤 문자 위치에 있을 경우 
 

 
DP[2][0] 이 'c'문자를 나타낸다고 하면,
'b'문자를 전송하고 마지막으로 있을 커서 위치 + 움직일 거리 만큼 버튼을 입력하기 때문에 
DP[2][0] = min(DP[1][0] + abs(b의 처음 인덱스 - c의 마지막 인덱스), DP[1][1] + abs(b의 마지막 인덱스 - c의 마지막 인덱스)
 
여기서 b의 처음 인덱스 - c의 마지막 인덱스인 이유는
첫번째 c의 인덱스에 위치하려면 오른쪽부터 갔다가 왼쪽으로 가야하기 때문임.
 
=> DP[i][0] = min(DP[i][0]+abs(b[0] - c.back()), DP[i][1]+abs(b.back()-c.back());
이런 공식이 되고, 
DP[i][1]도 동일하게 구해주면 된다.
 
설명을 잘 못해서... ㅜㅠ 이해가 잘 안가면 댓글....
 
[전체 코드]

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int DP[27][2];

int main() {
	vector<vector<int>> v(27); // 0:0, a:1, b:2 ... z:26
	string s;
	
	cin >> s;
	
	for (int i = 0; i < s.size();i++) {
		v[int(s[i] - 'a')+1].push_back(i);
	}
	v[0].push_back(0);

	DP[0][0] = 0;
	DP[0][1] = 0;

	int idx = 0;

	for (int i = 1;i < 27;i++) {
		if (v[i].empty()) {
			DP[i][0] = DP[i - 1][0];
			DP[i][1] = DP[i - 1][1];
			continue;
		}
		int F_E = abs(v[i][0] - v[i].back());
		int enter = v[i].size();
		DP[i][0] = min(DP[idx][0] + abs(v[idx][0] - v[i].back()), DP[idx][1] + abs(v[idx].back() - v[i].back()))+F_E+enter;
		DP[i][1] = min(DP[idx][0] + abs(v[idx][0] - v[i][0]), DP[idx][1] + abs(v[idx].back() - v[i][0]))+F_E+enter;
		idx = i;
	}

	cout << min(DP[26][0], DP[26][1]);


}

 
 
[고찰]
인덱스 실수가 있어서 한 번 코드를 갈아 엎었다. 
그리고 처음에 맨 앞 인덱스에서 끝나려면 맨 뒤부터 가야하는걸 생각을 못해서 이상하게 풀었던거 같음. 
그리고 0번에 더미값을 추가해줘야 for문이 예쁘게 돈다 ㅇㅇ 
 
++ cout<<DP[26] 으로 해놨는데, 이거 때문에 문제도 있었다. 그땐 비어있으면 DP를 그 전 인덱스 DP와 같이 만들어주는걸 안했어서 문제가 생겼었음, 추가로 idx 기록해주는거도 ㅇㅇ. 
 
++ vector의 back은 처음 써봣는데 갠춘하넹
 
++ 대망의 난독증 때문에 시간 낭비 개맣ㄴ이 함 ㅠㅠ ... 좀...;;;