23년 5월 9일 [알고리즘 - DP]

sua·2023년 5월 8일

알고리즘 가보자고

목록 보기

19/101

백준 11052번 카드 구매하기

문제

나의 풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int d[] = new int[n + 1];
        int p[] = new int[n + 1];

        for(int i = 1; i <= n; i++) {
            p[i] = sc.nextInt();
        }
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= i; j++) {
                d[i] = Math.max(d[i], d[i - j] + p[j]);
            }
        }

        System.out.println(d[n]);
    }
}

D[N] = 카드 N개를 구매하는 비용의 최대값이라고 한다.
D[N] = max(D[N - i] + p[i]) 로 점화식을 세울 수 있다.
i의 범위는 1 이상 N 이하이다.

결과

백준 16194번 카드 구매하기 2

문제

나의 풀이

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int p[] = new int[n + 1];
        for (int i=  1; i <= n; i++) {
            p[i] = sc.nextInt();
        }

        int[] d = new int[n + 1];
        for(int i = 1; i <= n; i++) {
            d[i] = -1;
            for(int j = 1; j <= i; j++) {
                if(d[i] == -1 || d[i] > d[i - j] + p[j]) {
                    d[i] = d[i - j] + p[j];
                }
            }
        }
        System.out.println(d[n]);
    }
}

앞선 문제에서 min으로 변경만 하면 될것 같지만 항상 배열 d에 0이 들어가기 때문에 카드를 구매하는 비용은 0보다 커서 min의 결과는 항상 0이 된다.
-> 배열의 초기값을 잘 설정해야 한다.

그래서 처음에 배열 d를 -1로 초기화시켜서 아직 정해지지 않았음을 의미하게 해준다.

for문에서 d[i]가 -1인 경우에 d[n - i] + p[i] 값으로 변경시키게 로직을 구현하면 된다.

결과

백준 15990번 1,2,3 더하기 5

문제

나의 풀이

import java.util.*;

public class Main {
    static final long mod = 1000000009L;
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        long d[][] = new long[100001][4];
        for(int i = 1; i <= 100000; i++) {
            if(i - 1 >= 0) {
                d[i][1] = d[i - 1][2] + d[i - 1][3];
                if(i == 1) {
                    d[i][1] = 1;
                }
            }
            if(i - 2 >= 0) {
                d[i][2] = d[i - 2][1] + d[i - 2][3];
                if(i == 2) {
                    d[i][2] = 1;
                }
            }
            if(i - 3 >= 0) {
                d[i][3] = d[i - 3][1] + d[i - 3][2];
                if(i == 3) {
                    d[i][3] = 1;
                }
            }
            d[i][1] %= mod;
            d[i][2] %= mod;
            d[i][3] %= mod;
        }

        int t = sc.nextInt();
        for(int i = 0; i < t; i++) {
            int n = sc.nextInt();
            System.out.println((d[n][1] + d[n][2] + d[n][3]) % mod);
        }
    }
}

연속을 처리하기 위해서
D[i][j] = i를 1,2,3의 합으로 나타내는 방법의 수, 마지막에 사용한 수는 j로 한다.
다음 수는 j와 같지 않은 수를 사용하라는 의미로 구분하기 위해 j를 사용한다.

D[i][1] = i를 1,2,3의 합으로 나타내는 방법의 수, 마지막에 사용한 수는 1
D[i][2] = i를 1,2,3의 합으로 나타내는 방법의 수, 마지막에 사용한 수는 2
D[i][3] = i를 1,2,3의 합으로 나타내는 방법의 수, 마지막에 사용한 수는 3

1번의 경우 바로 전에 사용할 수 있는 수는 2, 3이므로 2를 쓰고 1를 쓴 방법의 수인 D[i - 1][2]에 3을 쓰고 1를 쓴 방법의 수 D[i - 1][3]을 더해준다.
2번의 경우 바로 전에 사용할 수 있는 수는 1, 3이므로 1를 쓰고 2를 쓴 방법의 수는 D[i - 2][1]에 3을 쓰고 2를 쓴 방법의 수 D[i - 2][3]을 더해준다. 여기서 i - 2인 이유는 가장 마지막에 2를 더하면 i가 되는데 2를 제외하면 앞에서 더해줬던 모든 수의 합은 i - 2이기 때문이다.
3번의 경우 바로 전에 사용할 수 있는 수는 2, 3이므로 2를 쓰고 3을 쓴 방법의 수는 D[i - 3][2]에 3을 쓰고 1을 쓴 방법의 수 D[i - 3][1]을 더해준다.

최종적으로 식을 만들어 보면