[ PS ] 백준 25759, 들판 건너가기

문제 정보

• 문제 번호: BOJ 25759
• 문제 이름: 들판 건너가기
• 난이도: Gold
• 문제 링크: https://www.acmicpc.net/problem/25759

---

문제 요약

• 꽃의 개수 N이 주어진다.
• N개의 나열된 꽃 중에서, "인접한 꽃의 아름다움 차이"가 최대가 되도록 최적해를 찾는다.

---

처음 떠올린 아이디어

처음에는 DFS를 통해서, 분기 처리를 통해 구현할 수 있다고 생각했다. DFS로 구현하고 보니, DP로 뺄 수 있을 것 같아서 메모이제이션만 섞어서 Top-Down 방식으로 변경했다.

---

핵심 포인트

• Top-Down 방식으로 수행할 때, 퓨어 펑션을 만들기 위해 어떠한 인자를 들고 갈 것인지 정해야 한다.
• 점화식을 어떻게 세울 것인가? => 경우는 꽃의 갯수를 벗어나거나 이미 계산된 값이 있을 경우이다.
• solve(prev, idx)로 이전 상태와 현재 인덱스를 상태로 가져간다.

---

풀이 아이디어

기본적으로 DFS에 메모이제이션을 추가했다.

    public static int solveDFS(int prev, int idx) {
        if (idx >= N)
            return 0; // 현재 꽃을 고르지 않고 넘어감
        int nonePick = solve(prev, idx + 1);
        int pick; // 현재 꽃을 고르고 넘어감
        if (prev == 0) { // 이전에 고른 꽃이 없다면
            pick = solve(flowers[idx], idx + 1);
        } else {
            int score = (int) Math.pow(Math.abs(prev - flowers[idx]), 2);

            pick = score + solve(flowers[idx], idx + 1);
        }
        return Math.max(nonePick, pick);

    }

해당 코드가 DFS로 수행했던 코드이다. 이전 꽃이 없는 경우만 체크하고, 고르는 경우와 고르지 않는 경우 2가지 분기로 나누어 수행했다.

    public static int solve(int prev, int idx) {
        if (idx >= N)
            return 0;
        if (dp[prev][idx] != 0)
            return dp[prev][idx];

        // 현재 꽃을 고르지 않고 넘어감
        dp[prev][idx] = solve(prev, idx + 1);

        // 현재 꽃을 고르고 넘어감
        if (prev == 0) { // 이전에 고른 꽃이 없다면
            dp[prev][idx] = Math.max(dp[prev][idx], solve(flowers[idx], idx + 1));
        } else {
            int diff = prev - flowers[idx];
            int score = diff * diff;
            dp[prev][idx] = Math.max(dp[prev][idx], score + solve(flowers[idx], idx + 1));
        }

        return dp[prev][idx];
    }

해당 코드는 위의 DFS를 DP로 변경한 부분이다. 골격은 똑같고, dp배열에 담아서 진행한 점만 다르다.

1. 상태 정의

• dp[prev][idx] = idx번째 꽃부터 끝까지 확인할 때,
  직전에 선택한 꽃이 prev일 때 얻을 수 있는 최대 점수

2. 점화식

• 현재 꽃을 선택하지 않으면 다음 상태는 그대로 solve(prev, idx + 1)
• 현재 꽃을 선택하면 이전 꽃과의 점수를 계산한 뒤 solve(flowers[idx], idx + 1)로 이동
• 두 경우 중 최댓값을 저장한다

3. 기저 조건

• idx == N이면 더 이상 볼 꽃이 없으므로 0 반환

내가 헷갈렸던 부분

• 처음에는 누적합을 상태에 넣으려 했는데, 상태 수가 너무 커졌다.
• dp[idx] 하나로 처리하려 했지만, 이전에 고른 값에 따라 결과가 달라져서 잘못된 상태 정의였다.
• 처음에는 단순 DFS였고, 이후 메모이제이션을 추가해 Top-Down DP로 바꿨다.

---

정답 코드

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

/*
 * Top - Down  도전@@@@@@@@@@@
 * 
 * 상태공간트리에서 유지해야할 것.
 * 1. 이전 선택 꽃
 * 2. 현재 판단할 idx
 * 
 * 사이클이 돌지 않는 이유
 * idx가 +1로 넘어가기 때문
 * 
 * solve(prev, idx)
 * 
 * 기저 조건1 ) idx >= N;
 * 
 * dp의 축은 현재까지 탐색한 꽃의 갯수와 크기max를 축으로?
 * 
 */
public class Boj25759 {

    static int N;
    static int dp[][];
    static int[] flowers;

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

        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());
        flowers = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; ++i) {
            flowers[i] = Integer.parseInt(st.nextToken());
        }

        dp = new int[101][N];

        System.out.println(solve(0, 0));
    }

    public static int solve(int prev, int idx) {
        if (idx >= N)
            return 0;
        if (dp[prev][idx] != 0)
            return dp[prev][idx];

        // 현재 꽃을 고르지 않고 넘어감
        dp[prev][idx] = solve(prev, idx + 1);

        // 현재 꽃을 고르고 넘어감
        if (prev == 0) { // 이전에 고른 꽃이 없다면
            dp[prev][idx] = Math.max(dp[prev][idx], solve(flowers[idx], idx + 1));
        } else {
            int diff = prev - flowers[idx];
            int score = diff * diff;
            dp[prev][idx] = Math.max(dp[prev][idx], score + solve(flowers[idx], idx + 1));
        }

        return dp[prev][idx];
    }
//
//    public static int solveDFS(int prev, int idx) {
//        if (idx >= N)
//            return 0; // 현재 꽃을 고르지 않고 넘어감
//        int nonePick = solve(prev, idx + 1);
//        int pick; // 현재 꽃을 고르고 넘어감
//        if (prev == 0) { // 이전에 고른 꽃이 없다면
//            pick = solve(flowers[idx], idx + 1);
//        } else {
//            int score = (int) Math.pow(Math.abs(prev - flowers[idx]), 2);
//
//            pick = score + solve(flowers[idx], idx + 1);
//        }
//        return Math.max(nonePick, pick);
//
//    }
}