<stdio.han>

[문제 링크]

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

[난이도]

- Silver 2

[알고리즘]

- DP

[코드]

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

public class Main {
    static int[][][] dp = new int[51][51][51];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];


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

        int[] dp = new int[N];
        for (int i = 0; i < N; i++) {
            dp[i] = arr[i];
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + arr[i]);
                }
            }
        }
        int answer = 0;
        for (int i = 0; i < N; i++) {
            answer = Math.max(answer, dp[i]);
        }
        System.out.println(answer);
    }
}

[풀이]

LIS 알고리즘을 활용한 문제이다.

if (arr[j] < arr[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + arr[i]);
                }

dp[n] 은 arr[n]이 가장 큰 수인 증가하는 부분 수열일 때 증가하는 부분 수열의 합이다.

[문제 링크]

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

[난이도]

- Silver 2

[알고리즘]

- DP

[코드]

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

public class Main {
    static int[][][] dp = new int[51][51][51];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        while (true) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            if (a == -1 && b == -1 && c == -1) {
                break;
            }

            bw.write("w(" + a + ", " + b + ", " + c + ") = " + w(a, b, c) + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    static int w(int a, int b, int c) {
        if (a <= 0 || b <= 0 || c <= 0) {
            return 1;
        } else if (a > 20 || b > 20 || c > 20) {
            return w(20, 20, 20);
        } else if (dp[a][b][c] != 0) {
            return dp[a][b][c];
        } else if (a < b && b < c) {
            dp[a][b][c] =  w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
        } else {
            dp[a][b][c] = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
        }
        return dp[a][b][c];
    }
}

[풀이]

점화식은 이미 나와있기 때문에 고민할 필요는 없다. 다만 그대로 사용하면 시간초과가 발생한다. 이를 해결하기 위해

메모이제이션을 활용해야 한다. 함수는 다음과 같이 작성했다.

static int w(int a, int b, int c) {
        if (a <= 0 || b <= 0 || c <= 0) {
            return 1;
        } else if (a > 20 || b > 20 || c > 20) {
            return w(20, 20, 20);
        } else if (dp[a][b][c] != 0) {
            return dp[a][b][c];
        } else if (a < b && b < c) {
            dp[a][b][c] =  w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
        } else {
            dp[a][b][c] = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
        }
        return dp[a][b][c];
    }

아래 조건문을 활용하면 이미 한번 계산한 값이라면 저장해놓은 배열에서 꺼내서 사용할 수 있기 때문에 시간을 효율적으로 줄일 수 있다.

	else if (dp[a][b][c] != 0) {
            return dp[a][b][c];
        }

아래 조건문을 활용해 계산한 값을 dp 배열에 저장해 나중에 사용할 수 있다.

	else if (a < b && b < c) {
            dp[a][b][c] =  w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
        } else {
            dp[a][b][c] = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
        }

[문제 링크]

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

[난이도]

- Silver 3

[알고리즘]

- DP

[코드]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        int[] dp = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // DP 배열 초기화
        Arrays.fill(dp, 1);

        int max = 0;

        // LIS 알고리즘 적용
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(max, dp[i]);
        }

        // 결과 출력
        System.out.println(max);
    }
}

[풀이]

dp[n] = n번째 상자를 마지막으로 포함하는 가장 긴 부분수열

[문제 링크]

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

[난이도]

- Silver 3

[알고리즘]

- DP

[코드]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        long[] dp = new long[n + 1];

        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i - 2] + dp[i - 1]) % 10;
        }
        System.out.println(dp[n]);


        /**
         * dp[1] = 1
         * dp[2] = 2
         * dp[3] = 3
         * dp[4] = 5
         * dp[5] = 8
         * 피보나치 수열임
         */

    }
}

[풀이]

피보나치 수열의 마지막 자리 숫자만 출력하는 문제이다. 수를 10으로 나눈 나머지의 값이 마지막 숫자이다.

[문제 링크]

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

[난이도]

- Silver 3

[알고리즘]

- DP

[코드]

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

public class Main {
    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 == 1   (1)
         * 1
         *
         * n == 2   (2)
         * 1+1, 2
         *
         * n == 3   (4)
         * 1+1+1, 2+1, 1+2, 3
         *
         * n == 4   (7)
         * 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1
         *
         * n == 5   (13)
         * 1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, 1+2+2, 2+1+2, 2+2+1, 1+1+3, 1+3+1, 3+1+1, 2+3, 3+2
         *
         */

        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            int n = Integer.parseInt(br.readLine());
            int[] dp = new int[11];
            dp[1] = 1;
            dp[2] = 2;
            dp[3] = 4;
            for (int j = 4; j <= n; j++) {
                dp[j] = dp[j - 3] + dp[j - 2] + dp[j - 1];
            }
            bw.write(dp[n] + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

[풀이]

1. 초기값 설정

dp[1] = 1

dp[2] = 2

dp[3] = 4

2. 점화식 작성

dp[n] = dp[n-3]+dp[n-2]+dp[n-1]

[문제 링크]

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

[난이도]

- Silver 3

[알고리즘]

- DP

[코드]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            int n = Integer.parseInt(br.readLine());
            long[] dp = new long[102];

            dp[1] = 1;
            dp[2] = 1;
            dp[3] = 1;
            dp[4] = 2;
            dp[5] = 2;
            for (int j = 6; j <= n; j++) {
                dp[j] = dp[j - 1] + dp[j - 5];
            }
            System.out.println(dp[n]);
        }

        /**
         * dp[1] = 1
         * dp[2] = 1
         * dp[3] = 1
         * dp[4] = 2
         * dp[5] = 2
         * dp[6] = 3 = dp[5] + dp[1]
         * dp[7] = 4 = dp[6] + dp[2]
         * dp[8] = 5 = dp[7] + dp[3]
         * dp[9] = 7 = dp[8] + dp[4]
         * dp[10] = 9 = dp[9] + dp[5]
         * dp[11] = 12 = dp[10] + dp[6]
         * dp[12] = 16 = dp[11] + dp[7]
         *
         * dp[n] = dp[n-1] + dp[n-5]
         */

    }
}

[풀이]

1. dp 배열 정의

dp[1] = 1
dp[2] = 1
dp[3] = 1
dp[4] = 2
dp[5] = 2
dp[6] = 3 = dp[5] + dp[1]
dp[7] = 4 = dp[6] + dp[2]
dp[8] = 5 = dp[7] + dp[3]
dp[9] = 7 = dp[8] + dp[4]
dp[10] = 9 = dp[9] + dp[5]
dp[11] = 12 = dp[10] + dp[6]
dp[12] = 16 = dp[11] + dp[7]

2. 초기값 설정

dp[1] = 1
dp[2] = 1
dp[3] = 1
dp[4] = 2
dp[5] = 2

3. 점화식 작성

dp[n] = dp[n-1] + dp[n-5]

[문제 링크]

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

[난이도]

- Silver 2

[알고리즘]

- 매개변수 탐색

[코드]

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

public class Main {
    static int N, M;
    static long left = 1, right, answer = 0;
    static long[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        arr = new long[N];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            arr[i] = Long.parseLong(st.nextToken());
            right = Math.max(right, arr[i]);
        }

        parametricSearch();
        System.out.println(answer);
    }
    static void parametricSearch() {
        while (left <= right) {
            long mid = (left + right) / 2;
            if (M > getMid(mid)) { // M명 보다 적게나눠주면 길이를 과자의 길이를 줄여야 한다
                right = mid - 1;
            } else { // M명보다 많이 나눠줄 수 있거나 정확히 나눠줄 수 있으면 과자 길이를 늘려야 한다.
                left = mid + 1;
                answer = mid;
            }
        }
    }

    static int getMid(long mid) {
        int count = 0;
        for (long snack : arr) {
            count += snack / mid;
        }

        return count;
    }
}

[풀이]

입력받은 배열을 mid로 나눴을때의 몫의 수가 M보다 큰지 적은지를 판단해 left 와 right를 조절해준다.

[문제 링크]

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

[난이도]

- Silver 1

[알고리즘]

- 매개변수 탐색

[코드]

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

public class Main {
    static int N, M, left, right = 0, result = 0;
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            right += arr[i];
            left = Math.max(left, arr[i]);
        }

        parametricSearch();
        System.out.println(result);
    }
    static void parametricSearch() {
        while (left <= right) {
            int mid = (left + right) / 2;

            int sum = mid;
            int count = 0;
            if (M >= getMid(mid)) { // 인출한 횟수가 작거나 같으면 mid를 줄여야 한다
                result = mid;
                right = mid - 1;
            } else { // 인출한 횟수가 M보다 클 경우 mid를 늘려야 한다
                left = mid + 1;
            }
        }
    }

    static int getMid(int tmp) {
        //tmp = 한번에 인출할 수 있는 돈
        int count = 1; // 돈을 인출한 횟수
        int money = tmp; // 현재 남아있는 돈

        for (int num : arr) { // 하루에 사용할 금액 num
            money -= num; // 현재 남아있는 돈에서 사용할 금액을 뺀다
            if (money < 0) { // 0원보다 적어지면 다시 현금을 인출한다.
                count++; // 현금을 인출했으므로 count++
                money = tmp - num; // 0원보다 적어질 경우 남은 금액을 통장에 넣고 다시 인출하므로
            }
        }
        return count; // 인출한 횟수 리턴
    }
}

[풀이]

입력값을 정렬해서 푸는게 아니므로 이분탐색이 아닌 매개변수 탐색이다.

입력받은 arr배열을 돌면서 현재 보유한 돈에서 사용할 금액을 빼며 계산해준다. 현재 보유한 돈이 0보다 적어질 경우 남아있는 돈을 통장에서 넣고 인출하므로 count++ 해준다.

        for (int num : arr) { // 하루에 사용할 금액 num
            money -= num; // 현재 남아있는 돈에서 사용할 금액을 뺀다
            if (money < 0) { // 0원보다 적어지면 다시 현금을 인출한다.
                count++; // 현금을 인출했으므로 count++
                money = tmp - num; // 0원보다 적어질 경우 남은 금액을 통장에 넣고 다시 인출하므로
            }
        }