[BOJ] 문제 풀이 모음집 - DP (JAVA)

1463: 1로 만들기

🔗 문제 링크

• 1을 빼는 경우, 2로 나누는 경우, 3으로 나누는 경우를 각각 나누어서 점화식을 세워야 함
  • 1을 빼는 경우의 값으로 초기화: dp[i] = dp[i - 1]
  • 3으로 나누어지는 경우의 점화식: dp[i] = Math.min(dp[i], dp[i / 3] + 1)
  • 2로 나누어지는 경우의 점화식: dp[i] = Math.min(dp[i], dp[i / 2] + 1)
• BFS 탐색도 가능할 것 같아서 시도했는데 BFS 탐색으로도 최소 연산 횟수를 구할 수 있음
  • 탐색하고 있는 수가 1이 되면 탐색을 종료해야 함
  • dist[N]이 아니라, dist[1]의 값이 N에서 1까지의 최소 연산 횟수이므로 주의할 것!

24.06.24 풀이

위: BFS / 아래: DP

• DP 풀이

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[N + 1];
        dp[1] = 0;
        for (int i = 2; i <= N; i++) {
            // 1을 빼는 연산
            dp[i] = dp[i - 1] + 1;

            // 2로 나누어 떨어지면, 2로 나누는 연산
            if (i % 2 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            }

            // 3으로 나누어 떨어지면, 3으로 나누는 연산
            if (i % 3 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
            }
        }
        System.out.println(dp[N]);
    }
}

• BFS 풀이

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

public class Main {
    static int[] dist;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        dist = new int[N + 1];

        bfs(N);
        System.out.println(dist[1] - 1);
    }

    static void bfs(int x) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(x);
        dist[x] = 1; // 방문 처리를 위해 1을 대입 (출력할 때는 1을 빼줘야 함)

        while (!queue.isEmpty()) {
            int now = queue.poll();
            if (now == 1) break; // 1을 만들었다면 탐색 종료

            int next = now / 3;
            if (now % 3 == 0 && dist[next] == 0) { // 3으로 나누어지고 해당 수를 탐색하지 않은 경우
                queue.offer(next);
                dist[next] = dist[now] + 1;
            }

            next = now / 2;
            if (now % 2 == 0 && dist[next] == 0) { // 2로 나누어지고 해당 수를 탐색하지 않은 경우
                queue.offer(next);
                dist[next] = dist[now] + 1;
            }

            next = now - 1;
            if (dist[next] == 0) {
                queue.offer(next);
                dist[next] = dist[now] + 1;
            }
        }
    }
}

 

9095: 1, 2, 3 더하기

🔗 문제 링크

• 정수 5를 1, 2, 3의 합으로 나타내는 방법
  • 정수 4를 1, 2, 3의 합으로 나타내는 각 방법에 1을 더한 것
  • 정수 3을 1, 2, 3의 합으로 나타내는 각 방법에 2를 더한 것
  • 정수 2를 1, 2, 3의 합으로 나타내는 각 방법에 3을 더한 것
• 따라서 점화식은 다음과 같다
  • dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
  • 단, dp[1] = 1, dp[2] = 2, dp[3] = 4

24.06.25 풀이

import java.io.*;

public class Main {
    static int MAX = 11;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // DP 값 계산하기
        int[] dp = new int[MAX + 1];
        dp[1] = 1; dp[2] = 2; dp[3] = 4;
        for (int i = 4; i <= MAX; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }

        // 입력한 수에 맞는 DP 값 출력하기
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            int n = Integer.parseInt(br.readLine());
            sb.append(dp[n]).append("\n");
        }
        System.out.println(sb.toString());
    }
}

 

2579: 계단 오르기

🔗 문제 링크

• n번째 계단을 밟는 경우는 n - 1번째 계단을 밟는 경우와 밟지 않는 경우, 총 2가지로 나뉜다. (연속된 세 계단을 밟으면 안되므로)

• 위의 그림을 바탕으로 점화식을 세우면 다음과 같다
  • dp[i] = Math.max(dp[i - 3] + arr[n - 1], dp[i - 2]) + arr[i]
  • 단, dp[1] = arr[1], dp[2] = arr[1] + arr[2], dp[3] = Math.max(arr[1], arr[2]) + dp[3]

24.06.25 풀이

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n + 1];
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        for (int i = 1; i <= n; i++) {
            if (i == 1) dp[i] = arr[1];
            else if (i == 2) dp[i] = arr[1] + arr[2];
            else if (i == 3) dp[i] = Math.max(arr[1], arr[2]) + arr[3];
            else dp[i] = Math.max(dp[i - 3] + arr[i - 1], dp[i - 2]) + arr[i];
        }
        System.out.println(dp[n]);
    }
}

 

1149: RGB 거리

🔗 문제 링크

• 주어지는 비용의 정보가 2차원 배열 ⇒ 마찬가지로 dp도 2차원 배열을 사용하기
• 옆에 있는 집과 같은 색을 칠하면 안되므로, 현재 선택한 색이
  • 빨강인 경우 ⇒ 이전 집의 색은 초록이나 파랑
  • 초록인 경우 ⇒ 이전 집의 색은 빨강이나 파랑
  • 파랑인 경우 ⇒ 이전 집의 색은 빨강이나 초록

24.06.26 풀이

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][3];
        int[][] dp = new int[n][3];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < 3; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = arr[i][j];
            }
        }

        for (int i = 1; i < n; i++) {
            // 현재 집에 빨강을 칠하는 경우, 이전 집은 초록이나 파랑만 가능
            dp[i][0] += Math.min(dp[i - 1][1], dp[i - 1][2]);
            // 현재 집에 초록을 칠하는 경우, 이전 집은 빨강이나 파랑만 가능
            dp[i][1] += Math.min(dp[i - 1][0], dp[i - 1][2]);
            // 현재 집에 파랑을 칠하는 경우, 이전 집은 빨강이나 초록만 가능
            dp[i][2] += Math.min(dp[i - 1][0], dp[i - 1][1]);
        }

        System.out.println(Math.min(dp[n - 1][0], Math.min(dp[n - 1][1], dp[n - 1][2])));
    }
}

 

11726: 2×n 타일링 

🔗 문제 링크

• 2×5 직사각형을 1×2, 2×1 타일로 채우는 방법 (n = 5일 때)
  • 2×4 직사각형을 채우는 각각의 방법에 1×2 타일을 1개(| 모양) 붙인 것
  • 2×3 직사각형을 채우는 각각의 방법에 2×1 타일을 2개(= 모양) 붙인 것
• 따라서 이를 바탕으로 점화식을 세우면 다음과 같다
  • dp[i] = dp[i - 1] + dp[i - 2]
  • 단, dp[1] = 1, dp[2] = 2

24.06.26 풀이

import java.io.*;

public class Main {
    static final int MAX = 1_000;
    static final int DIV = 10_007;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[MAX + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % DIV;
        }
        System.out.println(dp[n]);
    }
}

 

11659: 구간 합 구하기 4

🔗 문제 링크

• dp 배열에는 1부터 현재 인덱스까지의 합을 기록하기
  • dp[i] = dp[i - 1] + arr[i]
• i번째 수부터 j번째 수까지의 합은 "1부터 j번째 수까지의 합 - 1부터 i-1번째 수까지의 합"과 같음
  • 따라서 i번째 수부터 j번째 수까지의 합을 구하는 식은 dp[j] - dp[i - 1]

24.06.26 풀이

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

public class Main {
    public static void main(String[] args) throws Exception {
        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());
        int[] arr = new int[n + 1];
        int[] dp = new int[n + 1];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            dp[i] = dp[i - 1] + arr[i];
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            // i번째 수부터 j번째 수까지의 합 = 1부터 j번째 수까지의 합 - 1부터 i-1번째 수까지의 합
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            sb.append(dp[b] - dp[a - 1]).append("\n");
        }
        System.out.println(sb.toString());
    }
}

 

12852: 1로 만들기 2

🔗 문제 링크

• 1로 만들기 문제와 동일하게 풀되, 새로운 배열을 하나 추가하여 어느 값을 사용해서 계산했는지 기록하기
  • ex) n = 10인 경우, dp[10] = 3, prev[10] = 9 (∵ 10 → 9 → 3 → 1) 

24.06.26 풀이

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[n + 1];
        int[] prev = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            if (i == 1) dp[1] = 0;
            else if (i == 2 || i == 3) {
                dp[i] = 1;
                prev[i] = 1;
            } else {
                dp[i] = dp[i - 1] + 1;
                prev[i] = i - 1;

                if (i % 3 == 0 && dp[i / 3] + 1 < dp[i]) {
                    dp[i] = dp[i / 3] + 1;
                    prev[i] = i / 3;
                }

                if (i % 2 == 0 && dp[i / 2] + 1 < dp[i]) {
                    dp[i] = dp[i / 2] + 1;
                    prev[i] = i / 2;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        sb.append(dp[n]).append("\n");
        sb.append(n).append(" ");
        int p = n;
        while (true) {
            if (prev[p] == 0) break;

            sb.append(prev[p]).append(" ");
            p = prev[p];
        }
        System.out.println(sb.toString());
    }
}

 

1003: 피보나치 함수

🔗 문제 링크

• 2차원 배열을 사용해서 f(n)을 호출할 때 출력하는 0과 1의 개수를 각각 기록함
• 점화식은 다음과 같음
  • dp[i][0] = dp[i-1][0] + dp[i-2][0]
  • dp[i][1] = dp[i-1][1] + dp[i-2][1]

24.06.27 풀이

import java.io.*;

public class Main {
    static final int N = 40;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[][] dp = new int[N + 1][2];
        dp[0][0] = 1; dp[1][1] = 1;
        for (int i = 2; i <= N; i++) {
            dp[i][0] = dp[i - 1][0] + dp[i - 2][0];
            dp[i][1] = dp[i - 1][1] + dp[i - 2][1];
        }

        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int t = 0; t < T; t++) {
            int n = Integer.parseInt(br.readLine());
            sb.append(dp[n][0]).append(" ").append(dp[n][1]).append("\n");
        }
        System.out.println(sb.toString());
    }
}

 

1932: 정수 삼각형

🔗 문제 링크

• (i, j)를 기준으로
  • 왼쪽 대각선 위에 있는 수의 위치는 (i - 1, j - 1)
  • 오른쪽 대각선 위에 있는 수의 위치는 (i - 1, j)
• 점화식은 다음과 같음
  • j = 0인 경우: dp[i][j] = dp[i - 1][j] + arr[i][j]
  • i, j가 같은 경우: dp[i][j] = dp[i - 1][j - 1] + arr[i][j]
  • 그 외의 경우: dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + arr[i][j] 

24.06.27 풀이

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); // 삼각형의 크기
        int[][] arr = new int[n][n];
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < i + 1; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = arr[i][j];
            }
        }

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i + 1; j++) {
                if (j == 0) {
                    dp[i][j] += dp[i - 1][j];
                } else if (i == j) {
                    dp[i][j] += dp[i - 1][j - 1];
                } else {
                    dp[i][j] += Math.max(dp[i - 1][j - 1], dp[i - 1][j]);
                }
            }
        }

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

 

11727: 2×n 타일링 2

🔗 문제 링크

• 2×n 타일링과 풀이 로직은 동일하지만, 2×2 타일을 만드는 방법이 2개라는 점이 다름
• 따라서 점화식은 다음과 같음
  • dp[i] = dp[i - 1] + dp[i - 2] * 2

24.06.27 풀이

import java.io.*;

public class Main {
    static final int DIV = 10_007;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            if (i == 1) dp[i] = 1;
            else if (i == 2) dp[i] = 3;
            else dp[i] = (dp[i - 1] + dp[i - 2] * 2) % DIV; // 2×2를 만드는 방법이 총 2개이므로
        }
        System.out.println(dp[n]);
    }
}

 

1912: 연속합

🔗 문제 링크

• 중요한 것은 "연속된 몇 개의 수"를 선택하는 것
• 연속해서 값을 더하는 것과 지금부터 새로 더하는 것을 비교해야 함
  • 연속해서 값을 더하는 것: dp[i] = dp[i - 1] + dp[i] (dp 배열에는 수열의 값이 저장되어 있음)
• 따라서 점화식은 다음과 같음
  • dp[i] = Math.max(dp[i], dp[i - 1] + dp[i])

24.06.27 풀이

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {
            dp[i] = Integer.parseInt(st.nextToken());
        }

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

 

11055: 가장 큰 증가하는 부분 수열

🔗 문제 링크

• 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 것이므로, 앞에서부터 수를 하나 정해서 해당 수보다 작은 것이 있는지 확인하면 됨 
  • 자신보다 작은 수가 있다면 해당 값을 이용해서 갱신하기: dp[i] = dp[i - 1] + arr[i]
  • 자신보다 작은 수가 없을 수 있기 때문에(=자신이 부분 수열의 시작인 경우), dp[i] = arr[i]로 초기화하고 탐색을 시작해야 함

dp[i] = arr[i]로 초기화 하는 부분을 생략해서 틀렸었다..ㅎ 제발 생각을 하고 풀자..!!!! 

24.06.27 풀이

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

public class Main {
    public static void main(String[] args) throws Exception {
        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[i] = arr[i];
        }

        int max = dp[0];
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) { // 증가하는 경우
                    dp[i] = Math.max(dp[i], dp[j] + arr[i]);
                }
            }
            max = Math.max(max, dp[i]);
        }
        System.out.println(max);
    }
}

 

11053: 가장 긴 증가하는 부분 수열

🔗 문제 링크

• 가장 큰 증가하는 부분 수열과 동일하게 풀면 됨
  • 다른 점은 증가하는 부분 수열의 최대 합이 아니라 증가하는 연속된 수의 최대값을 구하는 것
  • 따라서 dp 배열을 1로 초기화하고 시작해야 함 ({1}, {2}, ... 이런 식으로 자기 자신이 부분 수열에 포함되므로)

24.06.28 풀이

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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];
        dp[0] = 1;
        int maxLen = dp[0];
        for (int i = 1; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        System.out.println(maxLen);
    }
}

 

9461: 파도반 수열

🔗 문제 링크

• 삼각형의 규칙을 찾아 점화식을 세우면 쉽게 풀 수 있음
  • dp[i] = dp[i - 1] + dp[i - 5]
  • 단, dp[1] = dp[2] = dp[3] = 1, dp[4] = dp[5] = 2
• dp 배열을 long 타입으로 선언하지 않으면 오버플로우가 발생하므로 주의해야 함 
  • N = 100 & int 타입 ⇒ -203165375
  • N = 100 & long 타입 ⇒ 888855064897

24.06.28 풀이

 

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        int[] arr = new int[T];
        int max = 0;
        for (int i = 0; i < T; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            max = Math.max(max, arr[i]);
        }

        int[] dp = new int[max + 1];
        for (int i = 1; i <= max; i++) {
            if (i <= 3) dp[i] = 1;
            else if (i <= 5) dp[i] = 2;
            else dp[i] = dp[i - 1] + dp[i - 5];
        }

        StringBuilder sb = new StringBuilder();
        for (int a: arr) {
            sb.append(dp[a]).append("\n");
        }
        System.out.println(sb.toString());
    }
}

 

2748: 피보나치 수 2

🔗 문제 링크

• 피보나치를 구하는 식인 f(n) = f(n - 1) + f(n - 2)를 이용해서 점화식을 세우면 됨
• n이 최대 90까지 가능하므로 배열의 타입을 long으로 선언해야 함

24.06.29 풀이

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long[] dp = new long[n + 1];
        dp[0] = 0; dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        System.out.println(dp[n]);
    }
}

 

2193: 이친수

🔗 문제 링크

• 규칙을 알기 위해 직접 N자리 이친수의 개수를 구해보면 됨 (n이 1에서 5일 때까지)
  • 알게된 규칙: N자리 이친수의 개수는 N-1자리 이친수의 개수와 N-2자리 이친수의 개수를 더한 것과 같음
• N-2자리 이친수에 01을 붙인 것 + N-1자리 이친수에 0을 붙인 것 = N자리 이친수
  • 2자리 이친수: 10
  • 3자리 이친수: 100, 101
  • 4자리 이친수: 1000, 1001, 1010 (10+01, 100+0, 101+0)
• 따라서 점화식은 다음과 같음
  • dp[i] = dp[i - 1] + dp[i - 2]

24.06.30 풀이

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long[] dp = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            if (i <= 2) dp[i] = 1;
            else {
                dp[i] = dp[i - 1] + dp[i - 2];
            }
        }
        System.out.println(dp[n]);
    }
}

 

15988: 1, 2, 3 더하기 3

🔗 문제 링크

• 정수 4를 1, 2, 3의 합으로 나타내는 방법 (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1)
  • 정수 3을 1, 2, 3의 합으로 나타내는 방법 (=1+1+1, 1+2, 2+1, 3) + 1
  • 정수 2를 1, 2, 3의 합으로 나타내는 방법 (=1+1, 2) + 2
  • 정수 1을 1, 2, 3의 합으로 나타내는 방법 (=1) + 3

24.07.08 풀이

import java.io.*;

public class Main {
    static final int MAX = 1_000_000;
    static final int DIV = 1_000_000_009;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        int max = 0;
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            max = Math.max(max, arr[i]);
        }

        long[] dp = new long[MAX + 1];
        dp[1] = 1; dp[2] = 2; dp[3] = 4;
        for (int i = 4; i <= max; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % DIV;
        }

        StringBuilder sb = new StringBuilder();
        for (int a : arr) {
            sb.append(dp[a]).append("\n");
        }
        System.out.println(sb);
    }
}

 

14501: 퇴사 

🔗 문제 링크

• 1일부터 n일까지 각각 회의를 시작하면 얻을 수 있는 금액을 구하면 됨

어려워서 결국 답을 참고했다. 오랜만에 DP를 푸니까 너무 어렵다.. 많이 풀어보고 접하는 것이 답이니 노력하자..!

24.07.09 풀이

 

 

10844: 쉬운 계단 수 

🔗 문제 링크

• 0으로 끝나는 경우, 다음에 올 수 있는 것은 1개 (ex. 101, 201, ...)
• 9로 끝나는 경우, 다음에 올 수 있는 것은 1개 (ex. 198, 298, ...)
• 그 외의 경우로 끝나면 다음에 올 수 있는 것은 
• 점화식은 다음과 같음
  • dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]
  • 단, dp[i][0] = dp[i - 1][1], dp[i][9] = dp[i - 1][8]

24.07.09 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static final int DIV = 1_000_000_000;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		long[][] dp = new long[n + 1][10];
		for (int i = 1; i <= 9; i++) {
			dp[1][i] = 1;
		}

		for (int i = 2; i <= n; i++) {
			for (int j = 0; j <= 9; j++) {
				if (j == 0)
					dp[i][j] = dp[i - 1][j + 1] % DIV;
				else if (j == 9)
					dp[i][j] = dp[i - 1][j - 1] % DIV;
				else
					dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % DIV;
			}
		}

		long sum = 0;
		for (int i = 0; i <= 9; i++) {
			sum += dp[n][i];
		}
		System.out.println(sum % DIV);
	}
}

 

14002: 가장 긴 증가하는 부분 수열 4

🔗 문제 링크

• 이차원 배열로 선언해서 어느 것으로부터 갱신했는지 기록하기

24.07.09 풀이

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());

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

		int[][] dp = new int[n][2];
		for (int i = 0; i < n; i++) {
			dp[i][0] = 1;
			dp[i][1] = -1;
		}
		
		int max = dp[0][0], maxIdx = 0;
		for (int i = 1; i < n; i++) {
			for (int j = 0; j < i; j++) {
				if (arr[i] > arr[j] && dp[i][0] <= dp[j][0]) {
					dp[i][0] = dp[j][0] + 1;
					dp[i][1] = j;
				}
			}
			if (max < dp[i][0]) {
				max = dp[i][0];
				maxIdx = i;
			}
		}

		StringBuilder builder = new StringBuilder();
		int now = maxIdx;
		while (now != -1) {
			builder.insert(0, arr[now] + " ");
			now = dp[now][1];
		}
		builder.insert(0, max + "\n"); 
		System.out.println(builder);
	}
}

 

2156: 포도주 시식 

🔗 문제 링크

• 계단 오르기 문제와 유사한 느낌
• 포도주를 선택하는 방법은 총 3가지가 존재함
  1. i번째 포도주 선택 O & i - 1번째 포도주 선택 O ⇒ 연속해서 3잔을 마시면 안되므로 i - 3번째 포도주를 선택해야 함
     • dp[i] = dp[i - 3] + arr[i - 1] + arr[i]
  2. i번째 포도주 선택 O & i - 2번째 포도주 선택 O
     • dp[i] = dp[i - 2] + arr[i]
  3. i번째 포도주 선택 X
     • dp[i] = dp[i - 1]
• 총 3가지 방법 중 최댓값을 dp[i]에 넣어주면 됨

그림으로 이해하기

24.07.11 풀이

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        int max = 0;
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            if (i == 1) dp[1] = arr[1];
            else if (i == 2) dp[2] = arr[1] + arr[2];
            else dp[i] = Math.max(dp[i - 1], Math.max(dp[i - 3] + arr[i - 1] + arr[i], dp[i - 2] + arr[i]));
            max = Math.max(max, dp[i]);
        }
        System.out.println(max);
    }
}

 

11052:  카드 구매하기

🔗 문제 링크

• 카드를 구매할 수 있는 경우
  • 카드 1개 구매 = 1
  • 카드 2개 구매 = 1 + 1 = 2
  • 카드 3개 구매 = 1 + 1 + 1 = 2 + 1 = 3
  • ...
• 즉, 카드를 n개 구매하는 경우에는 다음의 경우를 고려해야 함
  • 카드를 1개 선택한 후, n - 1개를 선택하는 경우
  • 카드를 2개 선택한 후, n - 2개를 선택하는 경우
  • ...
• 정리하자면 "n개의 카드를 구매하는 최대 비용 = n - i개의 카드를 구매하는 최대 비용 + 나머지 i개의 카드를 구매하는 비용"이므로, 점화식은 다음과 같음 
  • dp[n] = dp[n - i] + arr[i]

24.07.12 풀이

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

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

        int max = dp[1];
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] = Math.max(dp[i], dp[i - j] + arr[j]);
            }
            max = Math.max(max, dp[i]);
        }
        System.out.println(max);
    }
}