1. 문제

문제 설명

음수가 아닌 숫자로 채워진 m x n 격자가 주어지면 경로를 따라 모든 숫자의 합을 최소화하는 왼쪽 상단에서 오른쪽 하단까지의 경로를 찾으시오.

제한사항

• 아래 또는 오른쪽으로만 이동 가능하다

입출력 예

• input : [[1,3,1], [1,5,1], [4,2,1]]
  
• output : 7
  • 1 ➡ 3 ➡ 1 ➡ 1 ➡ 1

2. 아이디어

도저히 쉽게 문제를 해결할 수 있는 방법이 떠오르지 않았다
그래서 처음에 생각했었던 조합(Combination)을 구현해보기로 마음 먹었다
고등학교 졸업 후 오랜만에 쓸려니까 가물가물했다
[0][0]에서 [m][n]로 이동하기 위해 항상 오른쪽으로 n-1번, 아래쪽으로 m-1번을 이동한다
그래서 전체 이동 step인 n+m중에서 n-1개를 뽑아서 그때에는 오른쪽으로 이동하고 나머지의 경우에는 아래로 이동시켰다
혹시 좋은 풀이방법을 알고 계신 분은 살짝만이라도 댓글 달아주시면 감사하겠습니다ㅜㅜ

3. 코드

import java.util.ArrayList;
import java.util.Arrays;


public class minCostPath {

    static int[][] paths;
    static boolean[] visited;
    static ArrayList<Integer> list = new ArrayList<>();

    public static void combination(int[] path, boolean[] v, int start, int size, int n){

        if(n==0){
            for(int i = 0; i < size; i++){
                if(visited[i]) {
                    list.add(path[i]);
                }
            }
            return;
        }

        for(int i = start; i < size; i++){
            visited[i] = true;
            combination(path, v,i+1,size,n-1);
            visited[i] = false;
        }

    }
    public static int soulution(int[][] input){
        int row = input.length-1;
        int col = input[0].length-1;
        visited = new boolean[row*col];
        int p = 1;
        for(int i = 1; i < row * col + 1; i++){
            p = p * i;
        }
        paths = new int[p/(row*col)][row];
        //0 == move to Right, 1 == move to Down
        int[] moveRow = {0,1};
        int[] moveCol = {1,0};
        //오른쪽 또는 아래 방향으로 각각 몇 번씩 이동할 수 있는지 기록

        int[] arr_path = new int[row+col];//{0,1,2,3}
        for(int i = 0; i < arr_path.length; i++){
            arr_path[i] = i;
        }

        //아래로 이동하는 경우만 골라낸다
        combination(arr_path, visited, 0, arr_path.length, row);

        for(int i = 0,j = 0; i < list.size(); ) {
            for(int y = 0; y < row; y++){
                paths[j][y] = list.get(list.size()-1);
                list.remove(list.size()-1);
            }
            j++;
        }

        int output = input[0][0];
        int curRow = 0;
        int curCol = 0;
        int minOutput = 0;
        for(int i : input[0]){
            minOutput += i;
        }
        for(int i = 0; i < input.length; i++){
            minOutput += input[i][input.length-1];
        }

        for(int i =0; i < paths.length; i++){
            Arrays.sort(paths[i]);
            int k = 0;
            for(int j = 0; j < row + col; j++){
                if(j == paths[i][k]){
                    curRow++;
                    k++;
                    output += input[curRow][curCol];
                    if(k==row) k = row-1;
                }
                else{
                    curCol++;
                    output += input[curRow][curCol];
                }
            }
            minOutput = Math.min(minOutput, output);
            curCol = 0;
            curRow = 0;
        }
        return minOutput;
    }

    public static void main(String[] args) {

        int[][] input = {{1,3,1},{1,5,1}, {4,2,1}};
        System.out.println(soulution(input));
    }

4. end...

하...이렇게 복잡한 문제가 아닌 거 같은데😥
그래도 이 기회에 조합을 구현하는 방법을 알게된 것을 위안 삼아야겠다...