백준 9465 스티커 - JAVA

9465 문제 링크

---

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

 

문제 설명

---

 

입출력

---

 

코드

---

<Bottom-up 방식>

import java.io.*;
import java.util.*;
 
public class Main {
    static int sticker;
    static int[][] arr;
    static int[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        sticker = Integer.parseInt(br.readLine());
        for (int s = 0; s < sticker; s++) {
            int num = Integer.parseInt(br.readLine());
            arr = new int[3][num+1];
            dp = new int[3][num+1];
            for (int i = 1; i < 3; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 1; j <= num; j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                } 
            } 
            dp[1][1] = arr[1][1];
            dp[2][1] = arr[2][1];
            sb.append(findMax(num)).append("\n");
        } 
        bw.write(sb.toString());
        bw.flush();
    }
    private static int findMax(int num) {
        int max = 0;
        for (int i = 2; i <= num; i++) {
            dp[1][i] = Math.max(dp[2][i-1], dp[2][i-2]) + arr[1][i];
            dp[2][i] = Math.max(dp[1][i-1], dp[1][i-2]) + arr[2][i];
        } 
        max = Math.max(dp[1][num], dp[2][num]);
        return max;
    }
}

 

<Top-down 방식>

import java.io.*;
import java.util.*;
 
public class Main {
    static int sticker;
    static int[][] arr;
    static int[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        sticker = Integer.parseInt(br.readLine());
        for (int s = 0; s < sticker; s++) {
            int num = Integer.parseInt(br.readLine());
            arr = new int[2][num];
            dp = new int[2][num];
            for (int i = 0; i < 2; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 0; j < num; j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                    dp[i][j] = -1;
                } 
            } 
            int result = Math.max(findMax(0, num-1), findMax(1, num-1));
            sb.append(result).append("\n");
        } 
        bw.write(sb.toString());
        bw.flush();
    }
    private static int findMax(int row, int col) {
        if (col < 0) {
            return 0;
        } 
        if (dp[row][col] != -1) {
            return dp[row][col];
        } 
        int pick = findMax(1-row, col-1) + arr[row][col];
        int skip = findMax(row, col-1);
        
        return dp[row][col] = Math.max(pick, skip);
    }
}

 

알고리즘 설명

---

여타 다른 DP문제들과 동일하게 바로 점화식을 구해야 하는 문제입니다. dp배열을 2차원 배열로 선언한 후, 해당 위치의 스티커를 선택할 지 아닐지에 따라 최댓값을 비교해 dp배열을 채워가는 간단한 문제입니다. 점화식은 아래와 같습니다.

해당 배열의 값을 선택한다면 다른 가로줄의 이전 세로줄에 누적된 최대값(dp[1-row][col-1])과 현재 선택한 원소의 값(arr[row][col])의 값을 더하고, 해당 배열의 값을 선택하지 않는다면, 해당 줄의 이전 세로줄에 누적된 최대값(dp[row][col-1])을 서로 비교하여야 합니다.

아래 arr배열과 dp배열을 표로 확인하면 확실하게 이해가 가실것입니다.

예제1의 첫번째 스티커

점화식으로 채운 dp 배열

탑다운과 바텀업 두 가지 방식으로 풀이가 가능하나 n의 크기가 10만이기 때문에, 탑다운 방식인 경우에 함수의 호출이 많아져 재귀호출 시, 스택프레임을 할당받고 해제하는 비용과 함수 자체의 호출 비용등을 고려했을 때, 바텀업(반복문)방식이 효율적이라고 할 수 있습니다. 점화식을 반복문과 재귀문에 내 입맛대로 적용할 수 있을 때까지 화이팅입니다...

 

코드 해석

---

스티커의 개수를 입력받아 테스트 케이스 개수를 저장하고, 각 테스트 케이스마다 스티커 점수를 저장할 배열과 DP 배열을 선언합니다. 이후 2행 n열의 스티커 점수를 입력받고, DP 배열의 첫 번째 열을 각각 초기화합니다. 이후 2열부터 마지막 열까지 순차적으로 탐색하면서, 현재 위치의 점수를 선택할 경우 대각선 방향의 이전 스티커 중 최댓값을 더해 DP 값을 갱신합니다. 최종적으로 마지막 열에서 두 행 중 더 큰 값을 찾아 결과를 출력합니다.