문제 이해 단계
https://school.programmers.co.kr/learn/courses/30/lessons/136797
입력으로 눌러야 하는 숫자가 순서대로 주어지고,
왼손과 오른손 엄지를 가지고 숫자를 눌러야 한다.
각 숫자를 누를 때마다 가중치라는 비용이 드는데
이는 위치에 숫자의 위치에 따라 달라진다.
조건은 아래와 같다.
- 이동하지 않고 제자리에서 다시 누르는 것 → 가중치 1
- 상하좌우 인접한 숫자로 이동 → 가중치 1
- 대각선으로 인접한 숫자로 이동 → 가중치 1
- 같지 않고 인접하지 않은 숫자를 누를 때
→ 위 규칙을 따라 가중치 합이 최소가 되는 경로
처음에 왼손은 4번, 오른손은 6번에서 시작한다.
이때, 나올 수 있는 가중치의 최소합을 구하는 문제
입력으로는 숫자만 들어온다.
문제 접근 단계
최소 가중치 계산법
여기서 구하라고 하는 것은 최소 가중치의 합이다.
눌러야 하는 숫자의 위치를 보고,
왼손과 오른손 중 더 가중치가 적은 것을 누르면 된다고 생각했다.
그렇기 때문에 일단은 두 지점 사이에
가중치의 최솟값을 구할 수 있어야 한다.
가중치의 순서로 보면, 정지 < 상하좌우 < 대각선 < 그 외이다.
두 지점이 일직선인지, 대각선인지,
겹치는지 아닌지에 대해 판단하면 된다.
제자리 : (x1, y1) == (x2, y2) 일 때 가중치 1
x와 y 중 하나의 좌표가 일치하면 된다.
즉, (x1 == x2 || y1 == y2) 일 때 가중치 2
즉, | x1 - x2 | == | y1 - y2 | 일 때 가중치 3
그 외는 어떻게 계산해야 할까?
여러 예시를 직접 해보면 알 수 있듯이
직진으로 갔다가, 한 칸만 대각선으로 가는 것이 최소비용이 드는 것이다.
그래서 두 좌표의 차를 해서 직선이 총 몇 칸 가야 하는지 구한다.
그리고 대각선으로 한 칸 간다.
식으로 나타내보면 이렇다.
MAX((x1-x2), (y1-y2)) - MIN((x1-x2), (y1-y2))
→ 가야 하는 직선 MIN((x1-x2), (y1-y2))
이런 식으로 계산한다.
최소 가중치의 합이 나오는 경우
이제 두 지점을 알면 최소 가중치의 합을 구할 수 있을까?
처음에는 다음 방법을 사용하려고 했다.
1. 다음에 눌러야 할 숫자의 좌표를 확인한다.
2. 현재 왼손과 오른손의 좌표를 확인한다.
3. 왼손과 타깃 지점, 오른손과 타깃 지점 중 가중치가 더 낮은 것의 좌표를 구한다.
4. 답에 해당 가중치를 더하고 선택된 가중치 쪽의 손을 숫자 쪽 좌표로 옮긴다.
5. 이 과정을 반복한다.
그런데 해당 방법은 예외 케이스가 있다는 것을 알았다.
(5,9,3) 순서로 입력할 때이다.
위의 논리대로라면 가중치를 기준으로 하기 때문에
같은 가중치일 때는 왼손과 오른손 중 아무거나 사용해도 상관없어야 한다.
초기 상태에서 왼손과 오른손은 5를 누를 때, 가중치는 2로 동일하다.
오른손으로 누르면 가중치의 최소합은 7이 된다.
위 방법으로는 이 문제를 해결할 수 없다.
나올 수 있는 경우의 수
위와 같은 상황이 언제 나올지도 모르고,
당장 가중치를 작은 것을 고르는 것이 최선이 아닐 수 있다.
그렇기 때문에 숫자가 주어졌을 때,
해당 번호를 왼손/오른손으로 누르는 경우를 따로 고려해야 한다.
이렇게 하면 많은 경우의 수가 나올 것이다.
예를 들어 총숫자가 3개가 주어진다면,
(왼, 왼, 왼), (왼, 오, 왼), (왼, 오, 오), (왼, 왼, 오),… 이런 식으로 말이다.
그런데 문제 제한사항에서
입력으로 들어올 수 있는 숫자의 개수는 총 100,000개까지이다.
100,000개가 되는 모든 경우의 수를 일일이 구하는 것은 분명히 시간초과가 날 것이다.
탐색 시간을 줄이거나, 최적화하는 방법을 찾아야 한다.
중복 탐색 줄이기(최적화)
나올 수 있는 경우의 수에 따라 시뮬레이션을 돌리는 것에서 힌트를 찾을 수 있었다.
나올 수 있는 경우에 따라 나눠서 구분하였다.
왼쪽 값은 왼손의 번호, 오른쪽은 오른손의 번호이다.
여기서 알 수 있는 것은 계산을 진행하다 보면,
경우의 수를 다르게 진행하여도 왼손과 오른손의 위치가 동일한 지점이 생긴다.
위 그림에서 각 색깔의 네모가 겹치는 지점이다.
돌려서 말하면 해당 부분이 중복 계산된다는 것이다.
즉 이러한 중복 계산을 방지한다면, 계산 속도를 높일 수가 있다.
그렇기 때문에 이 문제는 메모라이징 기법을 사용하는 DP처럼 해결한다.
DP 배열 만들기
DP 배열을 어떻게 만들어야 할까?
핵심은 왼쪽과 오른쪽과 함께 인덱스 번호까지 포함하여
3차원 배열을 만들어야 한다는 것이다.
왜냐하면 왼쪽과 오른쪽 손의 위치만 가지고 배열을 만들면,
다른 층(인덱스)에 있는 저장된 값과 겹쳐서 값이 다르게 나올 수 있기 때문이다.
DP [A][B][C] = K
A까지 탐색했고, 현재 왼손이 B번, 오른손이 C번에 있을 때의 최소 비용은 K
이제 이를 통해서 코드를 통해 구현하면 된다.
나머지는 문제 구현 단계를 통해 설명하겠다.
문제 구현 단계
C++로 구현한 코드
↓
#include <string>
#include <vector>
#include <cmath>
using namespace std;
// 좌표 구조체
struct Point{
int x,y;
};
// 숫자판
char map[4][3] = {{'1','2','3'},
{'4','5','6'},
{'7','8','9'},
{'*','0','#'}};
vector<Point> input; // 숫자 입력 순서
int dp[100001][10][10]; // dp 배열
// 두 점 사이의 최소 가중치를 계산하는 함수
int getWeight(Point pos, Point target){
int sx = pos.x;
int sy = pos.y;
int x = target.x;
int y = target.y;
// 두 점이 동일할 때(정지)
if(sx == x && sy == y) return 1;
// 상하좌우(일직선) 일 때
if(sx == x || sy == y) return abs((sx-x)*2 + (sy-y)*2);
// 대각선일때
if(abs(sx - x) == abs(sy - y)) return abs(sx-x)*3;
// 그 외 일 때
int nx = abs(sx-x);
int ny = abs(sy-y);
int diag = min(nx,ny);
int line = max(nx,ny);
return diag *3 + (line-diag)* 2;
}
// 시뮬레이션을 돌림
int startGame(Point left, Point right, int idx){
if(idx >= input.size()) return 0;// 인덱스를 다 돌았으면 종료
// left와 right의 좌표가 동일하면 안됨
if(left.x == right.x && left.y == right.y) return 9999999;
int l_num = map[left.x][left.y]-'0'; // 왼손의 현재 번호
int r_num = map[right.x][right.y]-'0'; // 오른손의 현재 번호
// dp 배열에 저장되어 있는 값이 있으면 바로 반환
if(dp[idx][l_num][r_num] != 0) return dp[idx][l_num][r_num];
//각 손으로 위치로 갔을 때의 최소 비용
int l_weight = getWeight(left,input[idx]);
int r_weight = getWeight(right,input[idx]);
// 해당 위치로 갔을 경우 최소 비용의 합
int v1 = l_weight + startGame(input[idx],right,idx+1);
int v2 = r_weight + startGame(left,input[idx],idx+1);
// 더 작은 값을 dp 배열로 저장
return dp[idx][l_num][r_num] = min(v1,v2);
}
int solution(string numbers) {
int answer = 0;
for(int k = 0; k < numbers.length(); k++){
for(int i = 0; i < 4; i++)
for(int j = 0; j < 3; j++)
// 입력값의 좌표를 찾아서 input에 저장
if(map[i][j] == numbers[k]) input.push_back({i,j});
}
Point left = {1,0}; // 왼손 초기 위치
Point right = {1,2}; // 오른손 초기 위치
answer = startGame(left,right,0);
return answer;
}↑
C#으로 구현한 코드
↓
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
List<Point> input = new List<Point>(); // 들어오는 입력 순서
// 숫자 키 판
char[,] map = new char[,]{{'1','2','3'},
{'4','5','6'},
{'7','8','9'},
{'*','0','#'}};
int[,,] dp = new int[100001,10,10]; // dp 배열
// 좌표를 정의한 클래스
public class Point
{
public int x{get;set;}
public int y{get;set;}
// 생성자
public Point(int x, int y){
this.x = x;
this.y = y;
}
}
// 두 점 사이의 최소 가중치를 계산하는 함수
public int GetWeight(Point pos, Point target){
int sx = pos.x;
int sy = pos.y;
int x = target.x;
int y = target.y;
// 두 점이 동일할 때(정지)
if(sx == x && sy == y) return 1;
// 상하좌우(일직선) 일 때
if(sx == x || sy == y) return Math.Abs((sx-x)*2 + (sy-y)*2);
// 대각선일때
if(Math.Abs(sx - x) == Math.Abs(sy - y)) return Math.Abs(sx-x)*3;
// 그 외 일 때
int nx = Math.Abs(sx-x);
int ny = Math.Abs(sy-y);
int diag = Math.Min(nx,ny); // 대각선의 길이
int line = Math.Max(nx,ny);
return diag *3 + (line-diag)* 2;
}
// 시뮬레이션을 돌림
public int StartGame(Point left, Point right, int idx){
if(idx >= input.Count) return 0; // 인덱스를 다 돌았으면 종료
// left와 right의 좌표가 동일하면 안됨
if(left.x == right.x && left.y == right.y) return 99999999;
int left_num = map[left.x,left.y] - '0'; // 왼손의 현재 번호
int right_num = map[right.x,right.y] - '0'; // 오른손의 현재 번호
// dp 배열에 저장되어 있는 값이 있으면 바로 반환
if(dp[idx,left_num,right_num] != 0) return dp[idx,left_num,right_num];
int l_weight = GetWeight(left,input[idx]); // 왼손으로 해당 위치로 갔을 때 최소값
int r_weight = GetWeight(right,input[idx]); // 오른손으로 해당 위치로 갔을 때 최소값
int result;
// 왼손으로 이동했을 경우의 최소 비용의 합
int v1 = l_weight + StartGame(input[idx],right,idx+1);
// 오른손으로 이동했을 경우의 최소 비용의 합
int v2 = r_weight + StartGame(left,input[idx],idx+1);
result = Math.Min(v1,v2); // 더 작은 값을 result
return dp[idx,left_num,right_num] = result; // 해당 값을 dp로 저장
}
public int solution(string numbers) {
char[] arr = numbers.ToCharArray(); // string을 char 리스트로 변환
for(int k = 0; k < arr.Length; k++){
for(int i = 0; i < map.GetLength(0); i++){
for(int j = 0; j < map.GetLength(1); j++){
// 입력값의 좌표를 찾아서 input에 저장
if(map[i,j] == arr[k]) input.Add(new Point(i,j));
}
}
}
int answer = 0;
Point left = new Point(1,0); // 왼손의 초기 위치
Point right = new Point(1,2); // 오른손의 초기 위치
answer = StartGame(left,right,0);
return answer;
}
}
↑
좌표를 편하게 나타내주기 위해 C++에서는 구조체로,
C#에서는 클래스로 Point를 만들어줬다.
dp 배열의 2번째 3번째 10,10인 이유는
자판이 0 ~ 9까지 있기 때문에 이를 표현해 주기 위함이다.
그리고 경우의 수를 분리하는 과정에서
왼손과 오른손이 같은 위치에 있을 수 있기 때문에
이러한 경우의 예외케이스를 지정해줘야 한다.
그 외엔 다 위에서 설명한 부분이고, 나머진 다 구현적인 부분이어서
코드에 적힌 주석으로 이해하는 것이 더 편할 것이다.
여기까지 하고 포스팅을 끝내겠다.
시행착오
백트래킹을 하면 안 될 거 같아서 고민하다가
결국 사용했는데... 시간초과질문게시판을 찾아보다 보니,
이 문제에 DP를 섞어야 한다는 것을 알았다.
그렇게 DP를 좀 생각하다 보니 어떻게 푸는지를 알아서 풀 수 있게 되었다.
푸는데 많이 오래 걸렸긴 한데, 그래도 풀었으니 다행이네.
생활비..