[백준] 9465번 스티커

문제링크: 백준 9465번 스티커

---

1. 아이디어

왼쪽부터 오른쪽으로 가면서 스티커 크기와 동일한 DP배열을 가지고 가면서 최대 값을 계속 계산해간 후, 마지막에서 최대값을 출력함.

[테스트 케이스]
50 10 100 20 40
30 50  70 10 60

• 예외처리

  • 열이 1개인 경우, 첫째 열의 첫 번째와 두 번째 값 중 최대값 출력.
  • 열이 2개인 경우, 첫째 열의 첫 번째와 둘째 열의 두 번째 값, 첫째 열의 두 번째 값과 둘째 열의 첫 번째 값(즉, 대각선) 중 최대값 출력.

• 열이 3개인 경우부터 DP배열에서 계산

  • 100 스티커가 있는 자리에는

    • 50(1열) - 50(2열) 스티커 선택한 경우, 즉 dp[1][1]
    • 30(1열) - 0(2열 선택 안함) 스티커 선택한 경우, 즉 dp[0][1]

    중 최대 값이 오게 됨.

  • 70 스티커가 있는 자리에는 그 반대의 경우가 됨.

---

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

public class Main {
    static int[][] sticker;
    static int[][] dp;
    static int times;
    static int width;

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

        times = Integer.parseInt(st.nextToken());

        for (int i = 0; i < times; i++) {

            st = new StringTokenizer(br.readLine());
            width = Integer.parseInt(st.nextToken());

            dp = new int[2][width];
            sticker = new int[2][width];

            for (int j = 0; j < 2; j++) {
                st = new StringTokenizer(br.readLine());
                for (int k = 0; k < width; k++) {
                    sticker[j][k] = Integer.parseInt(st.nextToken());
                }
            }

            if(width == 1) {
                System.out.println(Math.max(sticker[0][0], sticker[1][0]));
                continue;
            }

            dp[0][0] = sticker[0][0];
            dp[1][0] = sticker[1][0];
            dp[0][1] = dp[1][0] + sticker[0][1];
            dp[1][1] = dp[0][0] + sticker[1][1];

            if(width == 2) {
                System.out.println(Math.max(dp[0][1], dp[1][1]));
                continue;
            }

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

• 학습내용

  • 선택하고, 선택하지 않고 등이 번갈아가면서 길게 이어지는 경우에는 DP 배열을 활용하여 문제 접근이 가능!

  • 큰 문제를 부분 문제로 나눈 후 답을 찾아가는 과정!!

---

마지막 수정일시: 2022-11-22 14:35