메모이제이션 - 초콜릿과 건포도

서론

메모이제이션은 DP에서 많이 쓰이는 기법이다.

간단히 설명하면 문제를 계산하여 답을 저장하고, 이후에 겹치는 문제에 대해 계산을 하지 않고

저장된 답을 이용하는 것이다. 이는 영상처리 기법 중 하나인 LUT(Lookup Table)과 비슷하다.

이런 식으로 하면 빠른 실행 속도를 얻을 수 있지만 메모리 공간을 잃는다.

문제에 적용

문제:https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW9j-qfacIEDFAUY&categoryId=AW9j-qfacIEDFAUY&categoryType=CODE&&&

SW Expert Academy

알고리즘

1. 메모이제이션 할 배열 memo [][][][]를 선언한다. 4차원 배열로 선언한 이유는 변수 4개를 이용하여 나누기 때문이다.

2. 재귀를 이용한다. 종료조건은 나눠질 높이와 넓이가 1이 되면 종료되거나 저장된 값이 있으면 retrun 한다.

3. 가로로 자를 때와 세로로 자를 때를 나눈다. 계산을 다하면 memo를 return 한다.

구현 코드

class Solution_초콜릿과건포도
{
    static int N;
    static int M;
    static int map[][];
    static int memo[][][][];
    public static void main(String args[]) throws Exception
    {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(in.readLine().trim());
        for (int test_case = 1; test_case <= T; test_case++) 
        {
            StringTokenizer s = new StringTokenizer(in.readLine()," ");
            N = Integer.parseInt(s.nextToken());
            M = Integer.parseInt(s.nextToken());
            map = new int[N][M];
            memo = new int[N+1][M+1][N+1][M+1];
            for (int i = 0; i < N; i++) {
                s = new StringTokenizer(in.readLine()," ");
                for (int j = 0; j < M; j++) {
                    map[i][j] = Integer.parseInt(s.nextToken());
                }
            }
            //큰값으로 초기화
            for (int [][][] a1:memo) {
                for (int [][] a2:a1) {
                    for(int [] a3:a2) {
                        Arrays.fill(a3,Integer.MAX_VALUE);
                    }
                }
            }
            System.out.println("#"+test_case+" "+DFS(0,0,N,M));
        }
    }
    private static int DFS(int y, int x, int w, int h) { // 시작 좌표 y,x 높이 넓이 지정 min을 추가하면 메모이제이션 안써도 됌
        if(w == 1 && h==1) //종료조건
            return 0;
        if(memo[y][x][w][h] != Integer.MAX_VALUE) //메모배열에 값이 있으면 가지치기
            return memo[y][x][w][h];
        int sum=0;
        //나누기 전 건포도 값 더해야댐
        for (int i = y; i < y+w; i++) {
            for (int j = x; j < x+h; j++) {
                sum+=map[i][j];
            }
        }
        //가로로자름
        for (int k = 1; k <w ; k++) {
            int sum0 = DFS(y,x,k,h); //기준 위로 자름   sum0대신 memo[y][x][k][h]로 메모이제이션 해도됌
            int sum1 = DFS(y+k,x,w-k,h); // 아래로 자름
            memo[y][x][w][h] = Math.min(sum0+sum1+sum, memo[y][x][w][h]);
        }
        //세로로자름
        for (int k = 1; k <h ; k++) {
            int sum0 = DFS(y,x,w,k);
            int sum1 = DFS(y,x+k,w,h-k);
            memo[y][x][w][h] = Math.min(sum0+sum1+sum, memo[y][x][w][h]);

        }
        return memo[y][x][w][h];
    }    
}