SWEA[9282] - 초콜릿과 건포도[D4]

링크

SWEA[9282]

문제설명

• 완전탐색

문제풀이

• 완전탐색 -> 분할정복으로 재귀
• 시간초과 -> memoization 필요

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution9282 {

    public static int N;
    public static int M;
    public static int[][] map;

    public static int[][][][] mem;    

    public static int Cost(int[]src, int[]erc) {
        int cost=0;

        for (int i = src[0]; i <= erc[0]; i++) {
            for (int j = src[1]; j <= erc[1]; j++) {
                cost+=map[i][j];
            }
        }
        return cost;

    }

//    분할정복
    public static int Search(int[]src, int[]erc) {
//        1칸짜리로 남았을 경우  
        if(src[0]==erc[0] && src[1]==erc[1]) {
            return 0;
        }

        int now = Cost(src,erc);
        int sub = Integer.MAX_VALUE;
        int sub1;
        int sub2;

//        가로분할
        for (int i = src[0]; i < erc[0]; i++) {
            if (mem[src[0]][src[1]][i][erc[1]]==Integer.MAX_VALUE) {
                mem[src[0]][src[1]][i][erc[1]] = Search(new int[] {src[0],src[1]},new int[] {i,erc[1]});
            }

            if (mem[i+1][src[1]][erc[0]][erc[1]]==Integer.MAX_VALUE) {
                mem[i+1][src[1]][erc[0]][erc[1]] = Search(new int[] {i+1,src[1]},new int[] {erc[0],erc[1]});
            }

            sub = Math.min(sub, mem[src[0]][src[1]][i][erc[1]] + mem[i+1][src[1]][erc[0]][erc[1]]);
        }
//        세로분할
        for (int i = src[1]; i < erc[1]; i++) {
            if (mem[src[0]][src[1]][erc[0]][i]==Integer.MAX_VALUE) {
                mem[src[0]][src[1]][erc[0]][i] = Search(new int[] {src[0],src[1]},new int[] {erc[0],i});
            }

            if (mem[src[0]][i+1][erc[0]][erc[1]]==Integer.MAX_VALUE) {
                mem[src[0]][i+1][erc[0]][erc[1]] = Search(new int[] {src[0],i+1},new int[] {erc[0],erc[1]});
            }

            sub = Math.min(sub, mem[src[0]][src[1]][erc[0]][i] + mem[src[0]][i+1][erc[0]][erc[1]]);
        }

        mem[src[0]][src[1]][erc[0]][erc[1]] = now + sub;
        return mem[src[0]][src[1]][erc[0]][erc[1]];
    }

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("res/swea/9282.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        for (int test_case = 1; test_case <= T; test_case++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            map = new int[N][M];
            mem = new int[N][M][N][M];

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    for (int k = 0; k < N; k++) {
                        for (int l = 0; l < M; l++) {
                            mem[i][j][k][l] = Integer.MAX_VALUE;
                        }
                    }
                }
            }

            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < M; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            System.out.println("#"+test_case+" "+Search(new int[] {0,0}, new int[] {N-1,M-1}));
//            초기화
        }
    }
}

아쉬운점

• DFS 를 void 형식으로만 하려고 하니 bottom-up 과정에서 각각의 최소값 저장하려는게 구조짜기가 어려웠음.
  • minimum return 해주는 int 형식의DFS짜니 바로 해결.
• O(N)
  • 최대 2500개로 나눌 때, 2499번 나눠야함, 경우의 수 = 넉넉잡아 (나누는경우)*(map size) = 2499*2500
    • 6*10^6 = 시간초과 안걸리는데
  • 피보나치 처럼 반복 호출 할 경우가 생김
    • 시간초과의 원인
    • memoization 필요
      • 이게 필요한지 실전에서 판단할 수 있을까
• memoization 정의 잘못내림
  • 현재 가격만 저장하는게 아니라, 부분조각들의 모든 최소합을 저장함
  • 그래야 호출 줄일 수 있음

잘한점

• 재귀 구조는 제대로 짬
  • 탈출
  • 반복
    • 분할정복으로 재귀 잘 짰음