삼성 SDS 대학생 알고리즘 특강 10일차 - DP

7579: 앱

 

dp[totalCost]

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int dp[], m[], c[], N, M, totalCost = 0;
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        m = new int[N];
        c = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++)
            m[i] = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            c[i] = Integer.parseInt(st.nextToken());
            totalCost += c[i];
        }
        dp = new int[totalCost + 1];
        //dp[cost] = 앱들을 활성화한 비용이 cost일 때 확보한 최대 메모리 바이트 수
        for (int i = 0; i < N; i++) {
            //만약 c[0] -> totalCost 순으로 진행한다면, i번째 app을 여러 번 사용하는 결과 발생.
            //역순으로 진행해야 dp[j-c[i]]는 i번째 app을 사용하지 않은 cost임이 보장된다.
            for (int j = totalCost; j >= c[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - c[i]] + m[i]);
            }
        }
        int ans = -1;
        for (int i = 0; i <= totalCost; i++) {
            if (dp[i] >= M) {
                ans = i;
                break;
            }
        }
        System.out.println(ans);
    }
}

 

dp[N][totalCost]

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int dp[][], m[], c[], N, M, totalCost = 0;
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        m = new int[N];
        c = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++)
            m[i] = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            c[i] = Integer.parseInt(st.nextToken());
            totalCost += c[i];
        }
        dp = new int[N+1][totalCost + 1];
        for(int i = 1; i <= N; i++) {
            for(int j = 0; j <= totalCost; j++) {
                dp[i][j] = dp[i-1][j];
                if(j-c[i-1] >= 0) dp[i][j] = Math.max(dp[i][j], dp[i-1][j-c[i-1]] + m[i-1]);
            }
        }
        int ans = -1;
        for (int i = 0; i <= totalCost; i++) {
            if (dp[N][i] >= M) {
                ans = i;
                break;
            }
        }
        System.out.println(ans);
    }
}

 

11062: 카드게임

import java.io.*;
import java.util.*;

public class Main {
    static final int MAXN = 1000;
    static int T, N;
    static int[] A;
    static int[][][] dp;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        T = Integer.parseInt(br.readLine());

        A = new int[MAXN+1];
        dp = new int[2][MAXN+1][MAXN+1];
        for (int tc = 1; tc <= T; tc++) {
            N = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= N; i++) {
                A[i] = Integer.parseInt(st.nextToken());
                Arrays.fill(dp[0][i], 0);
                Arrays.fill(dp[1][i], 0);
            }

            //j = 구간 시작점
            //i = 구간 종료점
            for(int e = 1; e <= N; e++){
                for(int s = e; s > 0; s--){
                    for(int flag = 0; flag < 2; flag++) {
                        //마지막 근우차례로 끝날 때만 A[s] 더해줌.
                        if(s == e) {
                            dp[flag][s][e] = (flag == 0 ? A[s] : 0);
                            continue;
                        }
                        if(flag == 0) {
                            dp[flag][s][e] = Math.max(dp[1][s+1][e] + A[s], dp[1][s][e-1] + A[e]);
                        } else {
                            dp[flag][s][e] = Math.min(dp[0][s+1][e], dp[0][s][e-1]);
                        }
                    }
                }
            }
            int ans = dp[0][1][N];
            //int ans = dfs(1, N, 0);
            bw.write(ans+"\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    static int dfs(int start, int end, int flag) {
        if(start == end) return dp[flag][start][end] = (flag == 0 ? A[start] : 0);
        if(dp[flag][start][end] != 0) return dp[flag][start][end];
        if (flag == 0) 
            dp[flag][start][end] = Math.max(dfs(start + 1, end, 1) + A[start], dfs(start, end - 1, 1) + A[end]);
        else 
            dp[flag][start][end] = Math.min(dfs(start + 1, end, 0), dfs(start, end - 1, 0));
        return dp[flag][start][end];
    }
}

 

1102: 발전소

import java.io.*;
import java.util.*;

public class Main {
    static final int MAXN = 1000;
    static int N, P, X;
    static int D[][], dp[];
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        dp = new int[1<<N];

        Arrays.fill(dp, -1);

        D = new int[N+1][N+1];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                D[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int sts = 0;
        String str = br.readLine();
        for (int i = 0; i < N; i++) {
            char c = str.charAt(i);
            if(c == 'Y') sts |= 1 << i; 
        }
        P = Integer.parseInt(br.readLine());
        int ans = dfs(sts);
        bw.write(((ans > 999999) ? -1 : ans) + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    public static int bit_count(int sts) {
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            if ((sts & (1 << i)) > 0) cnt++;
        }
        return cnt;
    }

    public static int min_path(int sts, int to) {
        int ret = 999999;
        for (int from = 0; from < N; from++) {
            if ((sts & (1 << from)) > 0) {
                ret = Math.min(ret, D[from][to]);
            }
        }
        return ret;
    }

    public static int dfs(int sts) {
        int cost;
        if (bit_count(sts) >= P) return 0;
        if (dp[sts] != -1) return dp[sts];
        dp[sts] = 9999999;
        for (int to = 0; to < N; to++) {
            if ((sts & (1 << to)) == 0) {
                cost = min_path(sts, to);
                dp[sts] = Math.min(dp[sts], dfs(sts | (1 << to))+cost);
            }
        }
        return dp[sts];
    }
}