[BOJ] 28단계 동적 계획법 2

1

11066

파일 합치기

파일을 합쳐 하나로 모으는 최소 비용을 구하는 문제

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

public class Main {

    static int[] dp;
    static int[][] min;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(reader.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < T; i++) {
            int N = Integer.parseInt(reader.readLine());
            StringTokenizer st = new StringTokenizer(reader.readLine());
            dp = new int[N + 1];
            min = new int[N + 1][N + 1];
            for(int j = 1; j <= N; j++) {
                dp[j] = dp[j - 1] + Integer.parseInt(st.nextToken());
            }
            sb.append(dp(0, N)).append("\n");
        }
        System.out.print(sb);
    }

    public static int dp(int x, int y) {
        if(x + 1 == y) {
            return 0;
        }
        if(min[x][y] == 0) {
            min[x][y] = Integer.MAX_VALUE;
            for(int i = x + 1; i <= y - 1; i++) {
                min[x][y] = Math.min(min[x][y], dp(x, i) + dp(i, y));
            }
            min[x][y] += dp[y] - dp[x];
        }
        return min[x][y];
    }

}

*파일 두 개보다 작은 단위까지 계산되지 않도록 초기 조건 설정

 

2

11049

행렬 곱셈 순서

행렬을 곱하는 최소 비용: 행렬을 곱하는 순서에 따라 달라짐

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static int[][] cnt;
    static int[][] matrix;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        matrix = new int[N][N];
        cnt = new int[N][N];
        for(int i = 0; i < N; i++) {
            String[] split = reader.readLine().split(" ");
            matrix[i][0] = Integer.parseInt(split[0]);
            matrix[i][1] = Integer.parseInt(split[1]);
        }
        System.out.print(dp(0, N - 1));
    }

    public static int dp(int x, int y) {
        if(x == y) {
            return 0;
        }
        if(cnt[x][y] == 0) {
            cnt[x][y] = Integer.MAX_VALUE;
            for(int i = x; i < y; i++) {
                cnt[x][y] = Math.min(cnt[x][y], dp(x, i) + dp(i + 1, y) + matrix[x][0] * matrix[i][1] * matrix[y][1]);
            }
        }
        return cnt[x][y];
    }

}

 

3

1520

내리막 길

상하좌우 이웃한 곳으로 이동 가능

제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램

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

public class Main {

    static int[][] map;
    static Integer[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(reader.readLine());
        int row = Integer.parseInt(st.nextToken());
        int col = Integer.parseInt(st.nextToken());
        map = new int[row][col];
        dp = new Integer[row][col];
        for(int i = 0; i < row; i++) {
            st = new StringTokenizer(reader.readLine());
            for(int j = 0; j < col; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        dp[0][0] = 1;
        System.out.println(dp(row - 1, col - 1));
    }

    static int dp (int x, int y) {
        if(dp[x][y] == null) {
            dp[x][y] = 0;
            if(x > 0 && map[x-1][y] > map[x][y]) {
                dp[x][y] += dp(x-1, y);
            }
            if(y > 0 && map[x][y-1] > map[x][y]) {
                dp[x][y] += dp(x, y-1);
            }
            if(x < map.length - 1 && map[x+1][y] > map[x][y]) {
                dp[x][y] += dp(x+1, y);
            }
            if(y < map[0].length - 1 && map[x][y+1] > map[x][y]) {
                dp[x][y] += dp(x, y+1);
            }
        }
        return dp[x][y];
    }

}

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

public class Main {

    static int[][] map;
    static Integer[][] dp;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(reader.readLine());
        int row = Integer.parseInt(st.nextToken());
        int col = Integer.parseInt(st.nextToken());
        map = new int[row][col];
        dp = new Integer[row][col];
        for(int i = 0; i < row; i++) {
            st = new StringTokenizer(reader.readLine());
            for(int j = 0; j < col; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        dp[0][0] = 1;
        System.out.println(dp(row - 1, col - 1));
    }

    static int dp (int x, int y) {
        if(dp[x][y] == null) {
            dp[x][y] = 0;
            for(int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx > -1 && ny > -1 && nx < map.length && ny < map[0].length) {
                    if(map[nx][ny] > map[x][y]) {
                        dp[x][y] += dp(nx, ny);
                    }
                }
            }
        }
        return dp[x][y];
    }

}

*첫 번째 코드의 if절을 반복문으로 표현