5. 퍼즐게임 (+ 2차원 DP)

// 	 퍼즐게임 
// 	 2장의 카드가 남을 때 까지 반복해서 뽑는다 -> (뽑은 카드)*(뽑은 왼쪽 카드)*(뽑은 오른쪽 카드) 결과를 더한다.

//    나열된 카드 중에서 맨 왼쪽 카드와 맨 오른쪽 카드는 뽑아서는 안된다.
//    맨 마지막 동작을 하고 나면, 두 장의 카드가 남는다.

//    당신의 목표는 동작을 모두 하고나서, 각 동작의 점수의 합이 최소가 되도록 동작

+) 세련된 풀이
: 동적계획법

dy[i][j] : i번째부터 j번째까지의 까지의 부분수열을 게임동작했을 때 얻을 수 있는 최소 점수

package Q5;

import java.util.*;
class Main2 {
    public int solution(int[] nums){
        int n=nums.length;
        int[][] dy = new int[n][n];
//        for(int i=1; i<n-1; i++){
//            dy[i-1][i+1]=nums[i-1]*nums[i]*nums[i+1];
//        }
//        for(int i=1; i<n-1; i++){
//            System.out.println("dy["+(i-1)+"]"+"["+(i+1)+"]"+dy[i-1][i+1]);
//        }
        for(int j=2; j<n; j++){
            for(int i=0; i<n-j; i++){
                dy[i][i+j]=Integer.MAX_VALUE;
                //System.out.println("dy["+(i)+"]"+"["+(i+j)+"]"+dy[i][i+j]);
                for(int k=i+1; k<i+j; k++){
//                    System.out.println("dy["+(i)+"]"+"["+(i+j)+"]="+dy[i][i+j]);
                    dy[i][i+j]=Math.min(dy[i][i+j], dy[i][k]+dy[k][i+j]+nums[i]*nums[k]*nums[i+j]);
//                    System.out.println("dy["+i+"]"+"["+k+"]"+"+dy["+k+"]"+"["+(i+j)+"]"+"="+(dy[i][k]+dy[k][i+j])+"+");
//                    System.out.println("nums["+i+"]*nums["+k+"]*nums["+(i+j)+"]="+(nums[i]*nums[k]*nums[i+j]));
//                    System.out.println("min="+dy[i][i+j]);
                    for(int m=0;m<n;m++){
                        for(int b=0;b<n;b++){
                            System.out.print(dy[m][b]+" ");
                        }
                        System.out.println();
                    }
                    System.out.println();
                }
            }
        }
        return dy[0][n-1];
    }

    public static void main(String[] args){
        Main2 T = new Main2();
        int[] arr1={10, 1, 50, 50, 20, 5};
        System.out.println(T.solution(arr1)); //3650
        
        int[] arr2={98, 56, 77, 19, 20, 85, 81, 72, 59, 19, 5, 40, 20, 55, 16, 63, 50, 59, 20, 9};
        System.out.println(T.solution(arr2)); //217795

    }
}

 

package Q5;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Main {
    // 퍼즐게임 ##
    // 2장의 카드가 남을 때 까지 반복해서 뽑는다 -> (뽑은 카드)*(뽑은 왼쪽 카드)*(뽑은 오른쪽 카드) 결과를 더한다.
//    양의정수가쓰여져있다. 플레이어가 나열된 카드 중에서 한 개를 빼는 동작을 하면,
//    점수가 계산되는데, 점수는 뺀 카드와 그 카드의 왼쪽카드, 오른쪽 카드를 세 개를 곱하면 얻는 점수가 된다.

//    나열된 카드 중에서 맨 왼쪽 카드와 맨 오른쪽 카드는 뽑아서는 안된다.
//    맨 마지막 동작을 하고 나면, 두 장의 카드가 남는다.

//    당신의 목표는 동작을 모두 하고나서, 각 동작의 점수의 합이 최소가 되도록 동작

    public static void main(String[] args) {
        int[] nums={10, 1, 50, 50, 20, 5};
        System.out.println(solve(nums));
    }
    private static int solve(int[] nums){
        int n=nums.length;
        //뽑을 수 있는 카드 기준, 구할 수 있는 최소 점수들의 인덱스
        //1부터 뽑으면 -> 그 다음 칸에 최소값 저장
        int[][] dy = new int[n][n];

        //dy배열은 부분 수열의 최소 점수를 담는 2차원 배열

        //뽑을 수 있는 카드 기준, 구할 수 있는 최소점수들의 인덱스
        for(int j=2; j<n;j++){
            //i번을 언제 뽑아야 최소점수가 되는지
            for(int i=0; i<n-j;i++){
                dy[i][i+j]=Integer.MAX_VALUE;
                //실제로 뽑을 카드 번호 인덱스
                for(int k=i+1; k<i+j; k++){
                    //이전까지 카드를 뽑았을 때 최소 점수+해당 번호 뽑았을 때 점수

                    //첫 카드를 뽑을 경우 최소점수
                    //j:2 -> i=0 -> k=1 : 1번카드 뽑았을 때
                    //j:2 -> i=1 -> k=2 : 2번카드 뽑았을 때
                    //j:2 -> i=2 -> k=3 : 3번카드 뽑았을 때
                    //j:2 -> i=3 -> k=4 : 4번카드 뽑았을 때

                    //두 번째 카드를 뽑을 경우 최소점수
                    //j:3 -> i=0 -> k=1, 2 : 2번카드 뽑고, 1번 뽑았을 때 / 1번카드 뽑고, 2번 뽑았을 때
                    //j:3 -> i=1 -> k=2, 3 : 3번카드 뽑고, 2번 뽑았을 때 / 2번카드 뽑고, 3번 뽑았을 때
                    //j:3 -> i=2 -> k=3, 4 : 4번카드 뽑고, 3번 뽑았을 때 / 3번카드 뽑고, 4번 뽑았을 때

                    //세 번째 카드를 뽑을 경우 최소점수
                    //j:4 -> i=0 -> k=1, 2, 3
                    //j:4 -> i=1 -> k=2, 3, 4

                    //네 번째 카드를 뽑을 경우 최소점수
                    //j:5 -> i=0 -> k=1, 2, 3, 4

                    //dy[i][k]+ dy[k][i+j] : 그 전까지 뽑은 최소점수
                    //dy[i][i+j] : i번을 언제 뽑아야 최소점수 = dy[i][i+1] + dy[i+1][i+j]+nums[i]*nums[i+1]*nums[i+j]
                    dy[i][i+j]=Math.min(dy[i][i+j], dy[i][k]+dy[k][i+j]+nums[i]*nums[k]*nums[i+j]);
                }
            }
        }
        return dy[0][n-1];
    }
}