백준 10468 숫자뽑기게임 - JAVA

10468 문제 링크

---

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

 

문제 설명

---

 

입출력

---

 

코드

---

import java.io.*;
import java.util.*;
 
public class Main {
    static int[] arr;
    static int[][] dp;
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input;
        StringBuilder sb = new StringBuilder();
 
        while (!(input = br.readLine()).equals("0")) {
            StringTokenizer st = new StringTokenizer(input);
            N = Integer.parseInt(st.nextToken());
            arr = new int[N];
            for (int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());
 
            dp = new int[N][N];
            for (int[] row : dp) Arrays.fill(row, -1);
            sb.append(findMaxScore(0, N - 1)).append("\n");
        }
        System.out.print(sb);
    }
    // 구간 [s, e]에서 얻을 수 있는 최대 점수
    static int findMaxScore(int s, int e) {
        if (e - s <= 1) return 0; // 구간에 2개 이하만 남으면 더 이상 제거 불가
        if (dp[s][e] != -1) return dp[s][e];
 
        int max = 0;
        for (int i = s + 1; i < e; i++) {
            // 코드에서 첫 findMaxScore 진입이라면 탑다운 방식으로,
            // 마지막 점수의 합은 s + i + e일 것이다라고 가정하고 반대로 진행
            int score = arr[s] + arr[i] + arr[e];
            max = Math.max(max, findMaxScore(s, i) + findMaxScore(i, e) + score);
        }
        return dp[s][e] = max;
    }
}

 

알고리즘 설명

---

처음 접한 플래티넘 문제인데 생각보다 쉽게보여 빠르게 풀 수 있을줄 알았지만, 문제를 읽고선 DP 문제라는 것을 전혀 눈치채지 못하고, 반복문, DFS 등 여러 방법을 고민하다가 꽤 오랜 시간을 허비한 문제입니다. 결국 백준의 알고리즘 분류 버튼을 눌러 “다이나믹 프로그래밍” 문제라는 것을 알게 되었습니다.

또, 이 문제에 어떻게 DP를 적용하지? 라는 생각에 볼펜잉크와 메모지를 많이 써버렸네요. 문제를 많이 풀고 해당 문제가 어떤 풀이방식을 원하는지 보는 눈을 키워야 할 것 같습니다. 아직 많이 부족하다는 증거겠지요...

이 문제는, 현재 구간 [s, e]에서 맨 처음(s)와 맨 끝(e)는 제거가 불가능한 위치이므로, 가운데 숫자 i를 기준으로 양쪽 구간을 나누고, 양 끝과 가운데 숫자를 더한 값을 좌우 구간의 최댓값과 더해가며 구간의 최댓값을 갱신하는 방식입니다. 구간 내 숫자가 3개 이상일 때만 선택이 가능하므로 조건을 설정하고, 재귀적으로 분할하며 탐색을 반복합니다. 이 문제의 점화식 코드는 아래와 같습니다.

 

$$dp[s][e] = max(dp[s][i] + dp[i][e] + arr[s] + arr[i] + arr[e])$$

 

개인적으로 해당 문제는, 처음엔 점화식을 이해하지 못하더라도, 가능한 모든 구간 조합을 고려하면서 최댓값을 갱신한다는 흐름을 파악하면 조금씩 감이 잡히지 않을까 생각합니다.

 

코드 해석

---

DP 배열은 인덱스 s부터 e까지의 구간에서 얻을 수 있는 최대 점수를 저장하는 용도로 사용됩니다. 계산이 아직 이루어지지 않은 상태를 나타내기 위해 모든 값을 -1로 초기화합니다.

이후, 구간의 길이가 2 이하라면 세 수를 고를 수 없으므로 종료하는 기준으로, 재귀함수를 진행하고, 만약 이미 계산된 구간이라면 저장된 값을 그대로 반환합니다. 계산이 필요한 경우에는 s와 e 사이의 인덱스를 가운데로 삼아 구간을 (s, i)와 (i, e)로 나누고, 각각의 구간에서 얻을 수 있는 최대 점수에 현재 선택된 세 수 arr[s], arr[i], arr[e]의 합(score)을 더하여 최댓값을 갱신해 나갑니다.

계산이 종료되면, 함수의 반환값을 출력합니다.