문제

https://school.programmers.co.kr/learn/courses/30/lessons/87694

---

입력

• 숫자로 이루어진 문자열 numbers

---

출력

• 최소한의 시간으로 타이핑을 하는 경우의 가중치 합

---

풀이

제한조건

• 1 ≤ numbers의 길이 ≤ 100,000

접근방법

DP

어렵다!

항상 그리디 하게 접근하기에는 함정이 많다.
당장의 비용은 크더라도 이후의 경우를 고려하면 이동해야하는 경우가 있다.

그렇다고 완전 탐색을 시도하자니, 숫자의 길이가 100,000 까지이다.
왼손과 오른손 2가지 경우가 존재하므로 엄청난 경우의 수가 나온다.

탐색하는 경우의 수를 한 번 그려서 생각해보자.

(a,b) => a : 왼손, b : 오른손

조금씩 그려가다 보면, 중복되는 조합들이 나온다.
즉, 다른 경우의 수로 진행하더라도 특정 단계에서 왼손과 오른손의 위치가 동일해지는 경우가 생긴다.

이런 케이스의 계산 과정을 줄여준다면, 연산 수를 줄일 수 있다.

dp[i][j][k] : i번째 숫자를 탐색하고, 왼손이 j, 오른손이 k일때의 최소 가중치

---

코드

class Solution {
	int[][] weight;
	int[][][] dp;
	final int MAX = 987654321;
	char[] arr;
	int len;

	public int solution(String numbers) {
		weight = new int[][] {
			{1, 7, 6, 7, 5, 4, 5, 3, 2, 3}, {7, 1, 2, 4, 2, 3, 5, 4, 5, 6}, {6, 2, 1, 2, 3, 2, 3, 5, 4, 5},
			{7, 4, 2, 1, 5, 3, 2, 6, 5, 4}, {5, 2, 3, 5, 1, 2, 4, 2, 3, 5}, {4, 3, 2, 3, 2, 1, 2, 3, 2, 3},
			{5, 5, 3, 2, 4, 2, 1, 5, 3, 2}, {3, 4, 5, 6, 2, 3, 5, 1, 2, 4}, {2, 5, 4, 5, 3, 2, 3, 2, 1, 2},
			{3, 6, 5, 4, 5, 3, 2, 4, 2, 1}
		};
		len = numbers.length();
		dp = new int[len + 1][10][10];
		arr = numbers.toCharArray();
		for (int i = 0; i <= len; ++i)
			for (int j = 0; j < 10; ++j)
				for (int k = 0; k < 10; ++k)
					dp[i][j][k] = MAX;

		dp[0][4][6] = 0;

		return getMoveCount(0, 4, 6);
	}

	private int getMoveCount(int idx, int left, int right) {
		if (idx == len)
			return 0;

		if (dp[idx][left][right] != MAX)
			return dp[idx][left][right];

		int target = arr[idx] - '0';

		// 왼손을 움직여서 오른손과 겹치치 않는다면, 움직여보자.
		int moveLeft = MAX;
		if (target != right)
			moveLeft = getMoveCount(idx + 1, target, right) + weight[left][target];

		// 오른손을 움직여서 왼손과 겹치치 않는다면, 움직여보자.
		int moveRight = MAX;
		if (target != left)
			moveRight = getMoveCount(idx + 1, left, target) + weight[right][target];

		// 최소 비용을 저장한다.
		dp[idx][left][right] = Math.min(moveLeft, moveRight);
		return dp[idx][left][right];
	}
}