숫자 타자 대회
문제 링크 : 숫자 타자 대회
문제 설명
위와 같은 모양으로 배열된 숫자 자판이 있습니다. 숫자 타자 대회는 이 동일한 자판을 사용하여 숫자로만 이루어진 긴 문자열을 누가 가장 빠르게 타이핑하는지 겨루는 대회입니다.
대회에 참가하려는 민희는 두 엄지 손가락을 이용하여 타이핑을 합니다. 민희는 항상 왼손 엄지를 4 위에, 오른손 엄지를 6 위에 두고 타이핑을 시작합니다. 엄지 손가락을 움직여 다음 숫자를 누르는 데에는 일정 시간이 듭니다. 민희는 어떤 두 숫자를 연속으로 입력하는 시간 비용을 몇몇 가중치로 분류하였습니다.
- 이동하지 않고 제자리에서 다시 누르는 것은 가중치가 1입니다.
- 상하좌우로 인접한 숫자로 이동하여 누르는 것은 가중치가 2입니다.
- 대각선으로 인접한 숫자로 이동하여 누르는 것은 가중치가 3입니다.
- 같지 않고 인접하지 않은 숫자를 누를 때는 위 규칙에 따라 가중치 합이 최소가 되는 경로를 따릅니다.
예를 들어 1 위에 있던 손가락을 0 으로 이동하여 누르는 것은 2 + 2 + 3 = 7 만큼의 가중치를 갖습니다.
단, 숫자 자판은 버튼의 크기가 작기 때문에 같은 숫자 버튼 위에 동시에 두 엄지 손가락을 올려놓을 수 없습니다. 즉, 어떤 숫자를 눌러야 할 차례에 그 숫자 위에 올려져 있는 손가락이 있다면 반드시 그 손가락으로 눌러야 합니다.
숫자로 이루어진 문자열 numbers가 주어졌을 때 최소한의 시간으로 타이핑을 하는 경우의 가중치 합을 return 하도록 solution 함수를 완성해주세요.
제한 사항
- 1 ≤ numbers의 길이 ≤ 100,000
- numbers는 아라비아 숫자로만 이루어진 문자열입니다.
입출력 예
| numbers | result |
|---|---|
| "1756" | 10 |
| "5123" | 8 |
풀이 방법
- 가장 작은 가중치를 가지는 순서를 찾는 것이 문제인데, 그리디하게 풀 수 없을까라고 생각을 해봤는데, 부분 최적 구조를 띄지 않는 것으로 보였다. 예시를 봤을 때, 처음에 왼쪽, 오른쪽 중에서 명확하게 지금 선택한 것이 다음에 영향을 끼치는 것으로 보여서 그리디 방법은 옳지 않아 보였다.
- 다음으로 bfs를 통해서 왼쪽이나 오른쪽으로 무조건 선택해서 가는 방법을 통해서 정답을 찾을까 했는데,
O(2^N)의 시간복잡도를 가지기 때문에 시간초과가 발생할 것으로 보였다. 따라서 DP 방법으로 문제를 해결하고자 했고, 시도횟수 * 왼손 * 오른손을 가지는 3차원 DP 벡터를 선언해서 문제를 풀었다. - 먼저 특정 숫자 키패드 u에서 v까지 도달하는 데 필요한 가중치를 계산하는 함수를 만들었다. dx, dy를 구하여서 둘 다 0이 아니라면 무조건 대각선으로 이동하는 것이 유리하다는 점과 하나의 값만 있다면 해당 값 * 2만큼 이동하면 된다는 점을 이용해서 계산했다.
- 처음 시작하는 지점만을 0으로 두고, 점차 위로 올라가면서 가장 가중치가 작게 나오는 값만을 찾아서 기록하게끔 구현했다. 그리고 주의할 점으로 왼손과 오른손이 동시에 같은 지점을 누르면 안 되기 때문에 같은 지점을 누르려고 하는 경우에는 계산을 못하게 했다.
-> 해당 문제 풀이는O(N*M^2)의 시간복잡도를 가질 것으로 보이고, N은 최대 100,000이고 M은 최대 10이기 때문에 알맞은 알고리즘으로 보인다. 다른 사람의 풀이를 보니, 특정 키를 누르는데 걸리는 가중치를 계산하는 함수를 쓰지 않고, 값을 미리 저장해서 함수를 중복해서 호출하지 않아도 되게 효율적으로 푸는 방법도 있는 것 같다.
구현
#include <string>
#include <vector>
#include <climits>
using namespace std;
int num[10][2] = {{3, 1}, {0, 0}, {0, 1}, {0, 2}, {1, 0}, {1, 1}, {1, 2}, {2, 0}, {2, 1}, {2, 2}};
int route(int u, int v){
if (u == v){
return 1;
}
pair<int, int> from = {num[u][0], num[u][1]};
pair<int, int> to = {num[v][0], num[v][1]};
int dx = abs(from.first - to.first);
int dy = abs(from.second - to.second);
int sum = 0;
while(dx > 0 && dy > 0){
sum += 3;
--dx; --dy;
}
while(dx > 0){
sum += 2;
--dx;
}
while(dy > 0){
sum += 2;
--dy;
}
return sum;
}
int solution(string numbers) {
int n = numbers.size();
vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(10, vector<int>(10, INT_MAX)));
dp[0][4][6] = 0;
for (int i = 0; i < n; ++i){
int k = numbers[i] - '0';
for(int l = 0; l < 10; ++l){
for(int r = 0; r < 10; ++r){
if (dp[i][l][r] == INT_MAX) continue;
// 왼손 이동
if(k != r){
dp[i+1][k][r] = min(dp[i+1][k][r], dp[i][l][r] + route(l, k));
}
// 오른손 이동
if(k != l){
dp[i+1][l][k] = min(dp[i+1][l][k], dp[i][l][r] + route(r, k));
}
}
}
}
int answer = INT_MAX;
for(int l = 0; l < 10; ++l){
for(int r = 0; r < 10; ++r){
answer = min(answer, dp[n][l][r]);
}
}
return answer;
}
게임 개발자를 향해..