회고

  • 전형적인 DP 문제.
  • dp[i] = max(dp[i-1] + v[i], dp[i-1] - v[i])  if, dp[i-1] + v[i] < M, 0< dp[i-1] - v[i])
  • 마지막 곡 의 dp[i] 값이 정답

풀이

https://www.acmicpc.net/problem/1495


문제

Day Of Mourning의 기타리스트 강토는 다가오는 공연에서 연주할 N개의 곡을 연주하고 있다. 지금까지 공연과는 다른 공연을 보여주기 위해서 이번 공연에서는 매번 곡이 시작하기 전에 볼륨을 바꾸고 연주하려고 한다.

먼저, 공연이 시작하기 전에 각각의 곡이 시작하기 전에 바꿀 수 있는 볼륨의 리스트를 만들었다. 이 리스트를 V라고 했을 때, V[i]는 i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨을 의미한다. 항상 리스트에 적힌 차이로만 볼륨을 바꿀 수 있다. 즉, 현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번 곡은 P+V[i]나 P-V[i] 로 연주해야 한다. 하지만, 0보다 작은 값으로 볼륨을 바꾸거나, M보다 큰 값으로 볼륨을 바꿀 수 없다.

곡의 개수 N과 시작 볼륨 S, 그리고 M이 주어졌을 때, 마지막 곡을 연주할 수 있는 볼륨 중 최댓값을 구하는 프로그램을 작성하시오. 모든 곡은 리스트에 적힌 순서대로 연주해야 한다.

입력

첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다.

출력

첫째 줄에 가능한 마지막 곡의 볼륨 중 최댓값을 출력한다. 만약 마지막 곡을 연주할 수 없다면 (중간에 볼륨 조절을 할 수 없다면) -1을 출력한다.



소스

import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
    public static int N;
    public static int S;
    public static int M;
    public static int[] V;
    public static boolean[][] dp;
 
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
 
        N = sc.nextInt();
        S = sc.nextInt();
        M = sc.nextInt();
 
        V = new int[N + 1];
        dp = new boolean[N + 1][M + 1];
 
        for (int i = 1; i <= N; i++) {
            V[i] = sc.nextInt();
        }
 
        for (int i = 0; i < N; i++) {
            Arrays.fill(dp[i], false);
        }
 
        // 초기값 설정
        dp[0][S] = true;
 
        for (int i = 1; i <= N; i++) {
            for (int v = 0; v <= M; v++) {
                if (dp[i - 1][v]) {
                    if (v + V[i] <= M) {
                        dp[i][v + V[i]] = true;
                    }
                    if (0 <= v - V[i]) {
                        dp[i][v - V[i]] = true;
                    }
                }
 
            }
        }
 
        int ans = -1;
        for (int v = 0; v <= M; v++) {
            if (dp[N][v]) {
                ans = Math.max(ans, v);
            }
        }
 
        System.out.println(ans);
 
        sc.close();
    }
}


저작자표시 비영리 변경금지

'스터디 > 알고리즘 문제풀이' 카테고리의 다른 글

[백준 2098] 외판원 순회  (0) 2018.11.26
[백준 9376] 탈옥  (0) 2018.11.26
[백준 14500] 테트로미노  (0) 2018.11.26
[백준 1102] 발전소  (0) 2018.11.26
[백준 1126] 같은 탑  (0) 2018.11.26

회고

  • 최대/최소 구하는 문제는 DFS 로
  • 기저 조건은 적어도 P개의 발전소가 고장나 있지 않도록 고친다
  • 그렇다면, 3 개의 발전소가 고장나 있지 않은 상태는 다양하다
    • 1, 0, 0, 1, 1
    • 0, 1, 1, 1, 0
    • 0, 0, 1, 1, 1
    • ...
  • 따라서 고장나 있지 않은 발전소 상태를 bit 값으로 표현 (발전소 최대 16개, 2^16)
  • dp[n][bit]
  • 이를 memoization 한다


풀이


문제

은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이가 들어오기 전까지 발전소를 고쳐놓지 못한다면, 은진이는 해고당할 것이다.


발전소를 고치는 방법은 간단하다. 고장나지 않은 발전소를 이용해서 고장난 발전소를 재시작하면 된다. 하지만, 이때 비용이 발생한다. 이 비용은 어떤 발전소에서 어떤 발전소를 재시작하느냐에 따라 다르다.


적어도 P개의 발전소가 고장나 있지 않도록, 발전소를 고치는 비용의 최솟값을 구하는 프로그램을 작성하시오.


입력

첫째 줄에 발전소의 개수 N이 주어진다. N은 16보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 발전소 i를 이용해서 발전소 j를 재시작할 때 드는 비용이 주어진다. i줄의 j번째 값이 그 값이다. 그 다음 줄에는 각 발전소가 켜져있으면 Y, 꺼져있으면 N이 순서대로 주어진다. 마지막 줄에는 P가 주어진다. 비용은 50보다 작거나 같은 음이 아닌 정수이고, P는 0보다 크거나 같고, N보다 작거나 같은 정수이다.


출력

첫째 줄에 문제의 정답을 출력한다. 불가능한 경우에는 -1을 출력한다.


소스

import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
    public static int N;
    public static int[][] dp;
    public static int[][] cost;
    public static int P;
 
    public static int minCost(int yCnt, int ySet) {
        // 만약 목표 갯수에 도달했으면 그만 찾음
        if (yCnt >= P) {
            return 0;
        }
 
        // memo 가 있으면 리턴
        if (dp[yCnt][ySet] >= 0) {
            return dp[yCnt][ySet];
        }
 
        // 엄청 큰 수로 초기화
        dp[yCnt][ySet] = 1000000000;
 
        for (int i = 0; i < N; i++) {
            if ((ySet & (1 << i)) == (1 << i)) { // i가 켜져있음
                for (int j = 0; j < N; j++) {
                    if (i == j || (ySet & (1 << j)) == (1 << j)) // j도 켜져있으면 스킵
                        continue;
 
                    // 켜져있지 않은 발전소를 찾아 다음 state 계산
                    dp[yCnt][ySet] = Math.min(dp[yCnt][ySet], minCost(yCnt + 1, ySet | (1 << j)) + cost[i][j]);
                }
            }
        }
 
        return dp[yCnt][ySet];
    }
 
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
 
        N = sc.nextInt();
 
        dp = new int[N + 1][1 << 16];
        cost = new int[N][N];
 
        // init
        for (int i = 0; i <= N; i++) {
            Arrays.fill(dp[i], -1);
        }
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cost[i][j] = sc.nextInt();
            }
        }
 
        char[] chars = sc.next().toCharArray();
        P = sc.nextInt();
 
        int ySet = 0;
        int yCnt = 0;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == 'Y') {
                ySet |= (1 << i);
                yCnt++;
            }
        }
 
        int ans = minCost(yCnt, ySet);
 
        System.out.println(ans == 1000000000 ? -1 : ans);
        sc.close();
    }
 
}


저작자표시 비영리 변경금지

'스터디 > 알고리즘 문제풀이' 카테고리의 다른 글

[백준 2098] 외판원 순회  (0) 2018.11.26
[백준 9376] 탈옥  (0) 2018.11.26
[백준 14500] 테트로미노  (0) 2018.11.26
[백준 1495] 기타리스트  (0) 2018.11.26
[백준 1126] 같은 탑  (0) 2018.11.26



회고

  • 어떤 값을 0번째부터 부터 하나씩 선택, 안선택 하는 문제는 DP 로 풀어야 함 (DFS)
  • 하지만 N 이 50이므로, recursive call 을 하게되면 stack overflow 발생..
    • memoization 이 필요
  • dp[사용한 조각 갯수][왼쪽 탑 높이][오른쪽 탑 높이] 이러면..
    • 50 * 500000 * 500000 헐
  • dp[N][diff] 로 푼다
  • dfs(n, diff) 아래 값 들 중 max
    1. dp[n][diff] 또는 
    2. dfs(n+1, diff)
    3. difs(n, arr[n] + diff)
    4. dfs(n , |diff - arr[n]|)

풀이

문제

홍준이는 N개의 직사각형 블록을 가지고 있다. 홍준이는 블록 위에 또다른 블록을 올려놓는 방식으로 탑을 만들 수 있다. 이때, 두 개의 탑을 만드는데, 이 두 탑의 높이가 같게 만드려고 한다. (각 탑은 적어도 한 개의 블록을 포함해야 한다) 홍준이는 되도록이면 탑의 높이를 최대로 하려고 한다. 그리고 모든 블록을 사용할 필요는 없다.

각 블록의 높이가 주어질 때, 홍준이가 만들 수 있는 탑의 높이의 최댓값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 조각의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 각 조각의 높이가 주어진다. 높이는 500,000보다 작거나 같은 자연수이고, 모든 조각의 높이의 합은 500,000을 넘지 않는다.

출력

첫째 줄에 문제의 정답을 출력한다. 불가능할 때는 -1을 출력한다.



소스

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static int N;
    public static int[][] dp;
    public static int[] arr;
    public static int inf = 1 << 20;

    public static int search(int n, int diff) {
        if (diff > 250000)
            return -inf;

        if (N == n) {
            if (diff == 0)
                return 0;
            else
                return -inf;
        }

        if (dp[n][diff] != -1)
            return dp[n][diff];

        // 아무 선택하지 않은 경우
        dp[n][diff] = search(n + 1, diff);

        // 차이를 더 벌리는 경우
        dp[n][diff] = Math.max(dp[n][diff], search(n + 1, diff + arr[n]));

        // 차이를 좁히는 경우
        if (arr[n] > diff) {
            dp[n][diff] = Math.max(dp[n][diff], diff + search(n + 1, arr[n] - diff));
        } else {
            dp[n][diff] = Math.max(dp[n][diff], arr[n] + search(n + 1, diff - arr[n]));
        }

        return dp[n][diff];
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        dp = new int[N + 1][250001];
        arr = new int[N + 1];

        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();

            Arrays.fill(dp[i], -1);
        }

        int ans = search(0, 0);
        System.out.println(ans > 0 ? ans : -1);

        sc.close();
    }

}


저작자표시 비영리 변경금지

'스터디 > 알고리즘 문제풀이' 카테고리의 다른 글

[백준 2098] 외판원 순회  (0) 2018.11.26
[백준 9376] 탈옥  (0) 2018.11.26
[백준 14500] 테트로미노  (0) 2018.11.26
[백준 1495] 기타리스트  (0) 2018.11.26
[백준 1102] 발전소  (0) 2018.11.26

+ Recent posts

티스토리툴바