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

1932: 정수삼각형

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

public class Main {
    static int[][] dp;
    static int[][] triangle;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        dp[0][0] = triangle[0][0];
        //점화식: dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
        for(int i=1; i<N; i++){
            for(int j=0; j<=i; j++){
                int lt = j-1 < 0 ? 0 : dp[i-1][j-1];
                int rt = dp[i-1][j];
                dp[i][j] = Math.max(lt, rt) + triangle[i][j];
            }
        }

        int max = 0;
        for(int i=0; i< N; i++){
            max = Math.max(dp[N-1][i], max);
        }
        System.out.println(max);
    }
}

 

11660: 구간 합 구하기5

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

public class Main {
    static int[][] dp;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        dp = new int[N+1][N+1];

        for(int y=1; y<=N; y++){
            st = new StringTokenizer(br.readLine());
            int sum = 0;
            for(int x=1; x<=N; x++){
                sum+= Integer.parseInt(st.nextToken());
                           //   전줄 + 이번줄 합
                dp[y][x] = dp[y-1][x] + sum;
            }
        }
        int y1, x1, y2, x2;
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            y1 = Integer.parseInt(st.nextToken());
            x1 = Integer.parseInt(st.nextToken());
            y2 = Integer.parseInt(st.nextToken());
            x2 = Integer.parseInt(st.nextToken());
            //범위 전체 합 - 범위 해당안되는 윗줄 - 범위 해당안되는 왼쪽줄 + 두번뺀 윗줄과 왼쪽줄의 교집합
            int result = dp[y2][x2] - dp[y1-1][x2] - dp[y2][x1-1] + dp[y1-1][x1-1] ;
            System.out.println(result);
        }
    }
}

 

11049: 행렬 곱셈 순서

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;
        int N = Integer.parseInt(br.readLine());
        int[] rows = new int[N+1];
        st = new StringTokenizer(br.readLine());
        rows[0] = Integer.parseInt(st.nextToken());
        rows[1] = Integer.parseInt(st.nextToken());
        for(int i = 2 ; i <= N; i++){
            st = new StringTokenizer(br.readLine());
            rows[i-1] = Integer.parseInt(st.nextToken());
            rows[i] = Integer.parseInt(st.nextToken());
        }
        int[][] dp = new int[N+1][N+1];

        //j = 구간 시작점
        //i = 구간 종료점
        //k = j <= k < i
        for(int i = 1; i <= N; i++){
            for(int j = i-1; j > 0; j--){
                int min = Integer.MAX_VALUE;
                for(int k = j; k < i; k++){
                    min = Math.min(min, dp[j][k]+dp[k+1][i]+rows[i]*rows[k]*rows[j-1]);
                }
                dp[j][i] = min;
            }
        }
        System.out.print(dp[1][N]);
    }
}

 

14003: 가장 긴 증가하는 부분 수열5

import java.io.*;
import java.util.*;
public class Main {
    static int N;
    static int[] LIS;
    public static int binarySearch(int left, int right, int x) {
        int mid;
        while(left < right) {
            mid = (left + right) / 2;
            if(x > LIS[mid]) left = mid + 1;
            else right = mid;
        }
        return right;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        int[] A = new int[N];
        StringTokenizer token = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(token.nextToken());
        }
        LIS = new int[N+1];
        LIS[0] = -1000000001;
        int length = 0;
        ArrayList<Integer> result = new ArrayList<>();
        int[] LISIndex = new int[N+1];
        for(int i = 1; i <= N; i++) {
            //LIS배열의 가장 마지막 원소보다 Ai가 크다면 LIS의 마지막 공간에 삽입
            if(LIS[length] < A[i-1]) {
                LIS[++length] = A[i - 1];
                LISIndex[i] = length;
            }
            //그렇지 않으면 이분탐색해서 LIS 중간에 삽입
            else {
                int index = binarySearch(1, length, A[i-1]);
                LIS[index] = A[i-1];
                LISIndex[i] = index;
            }
        }
        for(int i = N; i > 0 && length > 0; i--) {
            if(length == LISIndex[i]) {
                result.add(A[i-1]);
                length--;
            }
        }
        bw.write(result.size()+"\n");
        for(int i = result.size()-1; i >= 0; i--) {
            bw.write(result.get(i) + " ");
        }
        bw.flush();
        bw.close();
        br.close();
    }

}

 

2098: 외판원 순회

import java.io.*;
import java.util.*;
public class Main {
    private static final int INF = 16000001; //TSP의 최대값보다 더 큰 값.
    static int N;
    static int[][] adj;
    static int allVisited;
    private static int[][] dp;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        allVisited = (1 << N) - 1;
        adj = new int[N][N];
        dp = new int[16][allVisited];
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++) {
                adj[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for (int i = 0; i < N; i++) {
            Arrays.fill(dp[i], -1);
        }
        //0번 정점에서 시작해서 모든 정점 방문 후 다시 0번 정점으로 돌아오는 최소 비용
        //이 때 TSP의 해가 존재하면, 시작정점은 0이 아닌 다른 정점으로 해도 무조건 최적해임이 보장된다. (사이클이기 때문)
        System.out.println(dfs(0, 1));
    }

    //dp[cur][visit] : cur정점에서 visit(bitmask) 만큼 정점을 방문한 상태일 때,
    //                 나머지 정점 모두 방문 후 다시 0번 정점으로 돌아가는 최소비용
    public static int dfs(int cur, int visit) {
        if (visit == allVisited) return adj[cur][0] == 0 ? INF : adj[cur][0];
        if (dp[cur][visit] != -1) return dp[cur][visit];

        dp[cur][visit] = INF;
        for(int i = 0; i < N; i++) {
            int next = 1 << i;
            if(adj[cur][i] != 0 && ((visit & next) == 0)) {
                dp[cur][visit] = Math.min(dp[cur][visit], dfs(i, (visit|next)) + adj[cur][i]);
            }
        }
        return dp[cur][visit];
    }

}