https://school.programmers.co.kr/learn/courses/30/lessons/136797#
1 2 3
4 5 6
7 8 9
# 0 *
주어진 숫자들을 순서대로 입력할 때 드는 시간비용의 최소값 구하기
시간비용은 엄지가 이동하는 위치에 따라 달라진다.
- 현재 위치를 누를 때 : 1
- 인접한 상하좌우 이동해서 누를 때 : 2
- 인접한 대각선으로 이동해서 누를 때 : 3
- 왼손 엄지의 초기 위치 : 4
- 오른손 엄지의 초기 위치 : 6
같은 숫자 위에 두 엄지가 같이 있을 순 없다.
눌러야할 숫자 위에 엄지가 있으면 그 엄지로 눌러야 한다.제한사항
1 ≤ numbers의 길이 ≤ 100,000
numbers는 아라비아 숫자로만 이루어진 문자열입니다.
어떻게 풀지 몰라서 아래 풀이를 참고했다.
https://thdbs523.tistory.com/302
풀이 과정
최소값을 구하는 방식임으로
1. 완전탐색
부적합하다. 제한 사항이 100,000이므로 2^100,000이니까 백트레킹으로 중간에 유망성 판단 후 자른다 해도 힘들 것이다.
2. Greedy
부적합하다. 그리디를 사용하기 위해서는 탐욕적 선택 속성(현재의 최적 선택이 이후의 선택을 고려하지 않아도 결과적인 최적 선택이 되어야 한다.)과 최적 부분 구조(전체의 최적해가 부분의 최적해로 구성되어있다.)를 만족해야한다.
빠지기 쉬운 오류
n-1 번째의 수까지 입력할 때 드는 최소비용을 안다면 그 엄지들의 최종 위치에서 다음 n번째의 수를 입력할 때 드는 비용 중 최소가 되는 선택을 한다면 n 번째 수 까지의 최소비용을 구할 수 있다.
이렇게 착각 할 수 있다.
다음 수를 입력할 때 드는 비용은 현재 엄지들의 위치와 다음 수 그리고 왼쪽 엄지를 사용할지 오른쪽 엄지를 사용할지에 의해서 정해진다.
n-1 번째의 수까지 입력할 때 드는 최소 비용을 구했을 때 엄지들의 위치가 특정 된다. 엄지들의 위치에서 n 번째의 수를 입력할 때 드는 비용이 최소가 되는 부분을 구할 수 있지만,
n-1 번째의 수까지 입력할 때 드는 최소 비용보다 1이 큰 값을 가지는 엄지들의 위치가 있다고 해보자. 그런데 그 엄지들의 위치에서 n번째의 수를 입력할 때 드는 최소 비용이 위에서의 값보다 2이상 작다면 최종적으로 위에서 구한 최소비용보다 더 작을 것이다.
이렇듯 부분문제를 잘못 설정하게 되면 Greedy로 볼 수 있는데 Greedy의 탐욕적 선택 속성을 만족하지 않는다.
- 탐욕적 선택 속성을 만족하지 않는다.
선택을 하게되면 엄지의 위치가 변하게된다. 변한 위치에 따라서 다음 숫자를 누르는 비용이 달라지게 된다. 때문에 현재 최소의 선택을 한다고 해서 결과적으로 최적의 선택이라고 할 수 없다. ex(7,8,0,9,3)
3. DP
적합하다. 최적 부분 구조가 보인다.
부분 문제는 이렇다.
현재 입력해야할 수(number[idx])와 손가락 위치에서 마지막 수까지 입력할 때 드는 최소비용은 현재 입력해야할 수를 입력 할 때의 가중치(왼쪽 엄지와 오른쪽 엄지 각각 다른 가중치를 가짐)와 그 다음 입력해야할 수(number[idx+1])와 이동한 손가락 위치(number[idx]로 왼쪽 엄지나 오른쪽 엄지가 이동하여 입력했을 것)에서 마지막 수 까지 압력할 때 드는 최소 비용을 더하였을 때 왼쪽 엄지를 이동한 경우와 오른쪽 엄지를 이동한 경우 둘 중 최소값을 가진다.
move_left = w[left]number[idx]]+recurDP(idx+1,number[idx],right);
move_right = w[right]number[idx]]+recurDP(idx+1,left,number[idx]);
dp[idx][left][right] = Math.min(move_left, move_right);
재귀적인 DP를 사용해서 푼다면 또 문제가 있다. 사실 재귀 코드 풀이를 참고하여 제출 하였는데 잘 풀려서 그냥 넘어가려 했지만 제한 사항에 숫자의 길이가 100,000이다. 이거는 자바 재귀 스택이 10000이 안되기 때문에 100,000이 들어오면 안풀린다. 이클립스로 돌려보니까 스택오버플로우가 난다.
반복문을 활용한 DP로 수정해보았다. 다른 풀이를 보니까 bfs로도 풀던데 bfs라 하지만 DP의 메모이제이션을 자료구조로 대체한 듯 하다.
코드
제출 코드
class Solution {
static int dr[] = {0,1,0,-1};
static int dc[] = {1,0,-1,0};
static int dir[] = {-1,1,-1,1};
static int dic[] = {1,1,-1,-1};
static char[][] board = {{'1','2','3'}, {'4', '5', '6'}, {'7', '8', '9'}, {'*', '0', '#'}};
static int [][][] dp;
static int [][] w = new int [10][10];
static int[] number;
static int MAX = Integer.MAX_VALUE;
static int n;
public int solution(String numbers) {
int answer = 0;
n = numbers.length();
number = new int [n];
dp = new int [n][10][10];
for(int i = 0; i < n; i++){
number[i] = numbers.charAt(i) - '0';
for(int j = 0; j < 10;j++){
Arrays.fill(dp[i][j], MAX);
}
}
for(int i = 0; i < 10; i++){
for(int j = 0; j < 10; j++){
w[i][j] = 100;
}
}
for(int i = 0; i < 4; i++){
for(int j = 0; j<3; j++){
if(board[i][j] != '*' && board[i][j] != '#'){
bfs(i,j,board[i][j] -'0');
}
}
}
// answer = recurDP(0,4,6);
answer = iterativeDP(4,6);
return answer;
}
public void bfs(int sR, int sC, int num){
Queue<int[]>q = new LinkedList<>();
q.offer(new int[] {sR, sC, num, 0});
w[num][num] = 1;
while(!q.isEmpty()){
int[] now = q.poll();
for(int i = 0; i < 4; i++){
int nR = now[0] + dr[i];
int nC = now[1] + dc[i];
if(nR < 0 || nR >= 4 || nC < 0 || nC >= 3){
continue;
}
if(board[nR][nC] != '*' && board[nR][nC] != '#' && w[num][board[nR][nC] - '0'] > now[3] + 2 ){
w[num][board[nR][nC] - '0'] = now[3] + 2;
w[board[nR][nC] - '0'][num] = now[3] + 2;
q.add(new int [] {nR, nC, board[nR][nC]-'0',now[3] + 2});
}
}
for(int i = 0; i < 4; i++){
int nR = now[0] + dir[i];
int nC = now[1] + dic[i];
if(nR < 0 || nR >= 4 || nC < 0 || nC >= 3){
continue;
}
if(board[nR][nC] != '*' && board[nR][nC] != '#' && w[num][board[nR][nC] - '0'] > now[3] + 3 ){
w[num][board[nR][nC] - '0'] = now[3] + 3;
w[board[nR][nC] - '0'][num] = now[3] + 3;
q.add(new int [] {nR, nC, board[nR][nC]-'0',now[3] + 3});
}
}
}
}
static int recurDP(int idx, int left, int right){
if(idx == n){
return 0;
}
if(dp[idx][left][right] == MAX){
int move_left = MAX;
int move_right = MAX;
if(right != number[idx]){
move_left = w[left][number[idx]]+recurDP(idx+1,number[idx],right);
}
if(left != number[idx]){
move_right = w[right][number[idx]]+recurDP(idx+1,left,number[idx]);
}
dp[idx][left][right] = Math.min(move_left, move_right);
}
return dp[idx][left][right];
}
static int iterativeDP(int left, int right) {
for (int idx = n - 1; idx >= 0; idx--) {
for (int l = 0; l < 10; l++) {
for (int r = 0; r < 10; r++) {
int moveLeft = MAX;
int moveRight = MAX;
if (r != number[idx]) {
if(idx == n-1){
moveLeft = w[l][number[idx]];
}else{
moveLeft = w[l][number[idx]] + dp[idx + 1][number[idx]][r];
}
}
if (l != number[idx]) {
if(idx == n-1){
moveLeft = w[r][number[idx]];
}else{
moveRight = w[r][number[idx]] + dp[idx + 1][l][number[idx]];
}
}
dp[idx][l][r] = Math.min(moveLeft, moveRight);
}
}
}
return dp[0][left][right];
}
}이클립스 실험 코드
import java.time.Instant;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Random;
public class Solution {
static int dr[] = { 0, 1, 0, -1 };
static int dc[] = { 1, 0, -1, 0 };
static int dir[] = { -1, 1, -1, 1 };
static int dic[] = { 1, 1, -1, -1 };
static char[][] board = { { '1', '2', '3' }, { '4', '5', '6' }, { '7', '8', '9' }, { '*', '0', '#' } };
static int[][][] dp;
static int[][] w = new int[10][10];
static int[] number;
static int MAX = Integer.MAX_VALUE;
static int n;
public static void main(String[] args) {
long microsTimestamp = Instant.now().toEpochMilli() * 1000;
long timestamp = System.currentTimeMillis();
Random random = new Random();
StringBuilder result = new StringBuilder();
for (int i = 0; i < 100000; i++) {
int digit = random.nextInt(10);
result.append(digit);
}
String numbers = result.toString();
int answer = 0;
n = numbers.length();
number = new int[n];
dp = new int[n][10][10];
for (int i = 0; i < n; i++) {
number[i] = numbers.charAt(i) - '0';
for (int j = 0; j < 10; j++) {
for (int k = 0; k < 10; k++) {
dp[i][j][k] = MAX;
}
}
}
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
w[i][j] = 100;
}
}
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 3; j++) {
if (board[i][j] != '*' && board[i][j] != '#') {
bfs(i, j, board[i][j] - '0');
}
}
}
answer = iterativeDP(4, 6);
// answer = recurDP(0,4,6);
long timestamp2 = System.currentTimeMillis();
long microsTimestamp2 = Instant.now().toEpochMilli() * 1000;
System.out.println(answer);
System.out.println("마이크로초 단위 타임스탬프: " + (microsTimestamp2 - microsTimestamp));
System.out.println("밀리초 단위 타임스탬프: " + (timestamp2 - timestamp));
}
static void bfs(int sR, int sC, int num) {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[] { sR, sC, num, 0 });
w[num][num] = 1;
while (!q.isEmpty()) {
int[] now = q.poll();
for (int i = 0; i < 4; i++) {
int nR = now[0] + dr[i];
int nC = now[1] + dc[i];
if (nR < 0 || nR >= 4 || nC < 0 || nC >= 3) {
continue;
}
if (board[nR][nC] != '*' && board[nR][nC] != '#' && w[num][board[nR][nC] - '0'] > now[3] + 2) {
w[num][board[nR][nC] - '0'] = now[3] + 2;
w[board[nR][nC] - '0'][num] = now[3] + 2;
q.add(new int[] { nR, nC, board[nR][nC] - '0', now[3] + 2 });
}
}
for (int i = 0; i < 4; i++) {
int nR = now[0] + dir[i];
int nC = now[1] + dic[i];
if (nR < 0 || nR >= 4 || nC < 0 || nC >= 3) {
continue;
}
if (board[nR][nC] != '*' && board[nR][nC] != '#' && w[num][board[nR][nC] - '0'] > now[3] + 3) {
w[num][board[nR][nC] - '0'] = now[3] + 3;
w[board[nR][nC] - '0'][num] = now[3] + 3;
q.add(new int[] { nR, nC, board[nR][nC] - '0', now[3] + 3 });
}
}
}
}
static int iterativeDP(int left, int right) {
for (int idx = n - 1; idx >= 0; idx--) {
for (int l = 0; l < 10; l++) {
for (int r = 0; r < 10; r++) {
int moveLeft = MAX;
int moveRight = MAX;
if (r != number[idx]) {
if (idx == n - 1) {
moveLeft = w[l][number[idx]];
} else {
moveLeft = w[l][number[idx]] + dp[idx + 1][number[idx]][r];
}
}
if (l != number[idx]) {
if (idx == n - 1) {
moveLeft = w[r][number[idx]];
} else {
moveRight = w[r][number[idx]] + dp[idx + 1][l][number[idx]];
}
}
dp[idx][l][r] = Math.min(moveLeft, moveRight);
}
}
}
return dp[0][left][right];
}
static int recurDP(int idx, int left, int right){
if(idx == n){
return 0;
}
if(dp[idx][left][right] == MAX){
int move_left = MAX;
int move_right = MAX;
if(right != number[idx]){
move_left = w[left][number[idx]]+recurDP(idx+1,number[idx],right);
}
if(left != number[idx]){
move_right = w[right][number[idx]]+recurDP(idx+1,left,number[idx]);
}
dp[idx][left][right] = Math.min(move_left, move_right);
}
return dp[idx][left][right];
}
}생각
iterativeDP 내의 반복문에서 첫번째 반복문의 인덱스가 n-1 부터 시작하는 것이 조금 불편했다. 보통 dp의 인덱스는 1부터 시작에서 n으로 더해주는데 이건 문제 상황에서 주어진 인덱스가 반대로 되어있어서 그렇다. 사실 반대로 dp를 구해도 되지만 그렇게 되면 시작점이 트리구조에 리프노드가 되어서 리프노드가 (4,6)이 맞는지 판별도 해주어야되고 루트노드도 20개로 나와서 20개로 반복 해줘야한다.
목적지로 가는 최단 경로 문제
목적지로 가는 최단 경로를 구할 때 시작점에서 선택을 고려하는 것이 아니고 목적지에 들어오는 선택들을 중에서 최소 값을 구한다. 이걸 통해서 루트를 목적지로 두고 아래로 뻗어나가는 트리를 만들 수 있다.
사실 거꾸로 트리를 그려도 풀린다. 시작점으로 들어오는 선택 중 최소값을 구하는 형식으로 dp를 구현해도 된다. 두 노드는 고정에 연결되는 값중 최소 값을 찾는 거니까
피보나치 수열
피보나치 수열에서도 현재 항은 이전항과 그 이전의 항의 덧셈으로 표현된다. 트리구조를 그리면 루트에 현재 항을 대입하고 아래로 뻗어내려간다.
지금 문제
이 문제에서는 시작점에서 하나씩 눌러가는 선택을 한다. 얼핏 보면 목적지로 가는 최단 경로 문제와 같다고 생각된다. 하지만 목적지가 정확하게 특정되어 있지 않다. (모로가도 다 누르기만 하면 되고 예를들어 마지막이 7이면 (0,7), (1,7)...) 이런식으로 20개의 노드 중 하나에 도달하는게 조건이다. 그런데 위에서 봤듯이 거꾸로 진행되는 것도 상관 없다고 했으니 이런 상황 때문에 루트노드를 초기 선택(4,6)으로 해서 트리를 그려 푸는게 효율적이다.
