[Algorithm] 백준 DP문제 - 스티커(9465) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 DP 문제 모음 스티커 자바 풀이를 진행하고자 합니다.

 

문제출처: https://www.acmicpc.net/problem/9465

9465번: 스티커

 

1. 풀이 소스

 

import java.io.*;
import java.util.*;
import static java.lang.Integer.parseInt;

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

        Sticker sticker = new Sticker();
        for (int i = 0; i < t; i++) {
            int n = parseInt(br.readLine());
            sticker.setInit(n);
            for (int row = 0; row < 2; row++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int col = 1 ; col <= n; col++)
                    sticker.setMap(row, col, parseInt(st.nextToken()));
            }
            sticker.run();
        }

        sticker.printResult();

    }    
}

class Sticker {
    int n;
    int[][] dp;
    int[][] map;
    List<Integer> result = new ArrayList<>();
    
    Sticker () {
    }

    void setInit(int n) {
        this.n = n;
        dp = new int[2][n + 1]; // dp를 담을 2차원 배열 
        map = new int[2][n + 1]; // 각 스티커의 값
    }
    
    void setMap(int row, int col, int value) {
        map[row][col] = value; 
    }
    
    void run() {
        dp[0][1] = map[0][1]; // i가 2부터이므로 1을 초기화 
        dp[1][1] = map[1][1];
        
        for (int i = 2; i <= n; i++) {
            dp[0][i] = Math.max(dp[1][i - 1], dp[1][i - 2]) + map[0][i];
            dp[1][i] = Math.max(dp[0][i - 1], dp[0][i - 2]) + map[1][i];
        }
        result.add(Math.max(dp[0][n], dp[1][n]));
    }

    void printResult() {
        StringBuilder sb = new StringBuilder();

        for (Integer r : result) {
            sb.append(r).append("\n");
        }
        System.out.print(sb);
    }
}

 

2. 풀이 중점 사항

 

평소 DP가 약하여, 점화식을 도출하는 것에서 바로 떠오르지 않아 이러한 형태의 문제에서는 자동적으로 

현재 DP = Math.max(이전 DP, 이전*2 DP)를 적어놓고 문제를 다시 보곤 합니다.

 

이 문제에서 중점 사항은 면이 인접하지 않게 골라야 하므로, 현재 선택지에서 최댓값은 이전 인덱스의 DP의 최댓값이면서, 행이 다른 DP, 그리고 인덱스가 2개 적은 DP의 다른 행 DP의 최댓값을 비교한 후, 더 큰 것에 현재의 값을 구하는 방식입니다.

 

for (int i = 2; i <= n; i++) {
    dp[0][i] = Math.max(dp[1][i - 1], dp[1][i - 2]) + map[0][i];
    dp[1][i] = Math.max(dp[0][i - 1], dp[0][i - 2]) + map[1][i];
}
result.add(Math.max(dp[0][n], dp[1][n]));

 

이러한 코드가 가능한 이유는, 다음과 같습니다.

60 70 100 20

70 700 10 900 이 있다고 가정하겠습니다.

 

20의 입장에서 최대를 선택하는 것은 각 열에 인접하지 않게 선택하여 값을 늘리는 것입니다.

70 70 10 이 될 수 있고, 60 700 이 될 수 있습니다.

(60 700 100 은 20에 100이 인접하므로 될 수 없습니다. || 70 70은 10을  추가로 선택할 수 없으므로 최대값이 되지 못합니다.)

따라서, 점화식은 위의 코드와 같이 구성될 수 있습니다.

 

2차원 배열이므로, 위 아래 각각 DP를 적용하고, 최종적으로 마지막 인덱스에서 두 DP 중 더 큰 값을 선택하여 값을 도출할 수 있습니다.

 

이상으로 스티커 자바 풀이를 마치도록 하겠습니다. 감사합니다.!!