백준 [16297] Eating Everything Efficiently

DP + 위상 정렬 문제

수학적 센스가 필요한 문제다.

DFS로도 풀 수 있다.

 

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

16297번: Eating Everything Efficiently

 

문제를 요약하자면, 단방향 그래프에서

피자를 먹기로한 첫 노드에선 피자를 다 먹고

그 다음 노드에서 피자를 먹을려면 1 / 2^(k-1) 만큼 먹는다.

즉, 첫 노드에선 피자 한 판 다 먹고, 그 다음 노드 부턴 이전에 먹은 피자 크기의 절반씩만 먹는다.

 

예시 1을 도식화하면 다음과 같다.

검은 글씨는 노드 번호

빨간 글씨는 해당 피자를 먹을 때의 만족도다.

예시 1 도식화

 

처음 생각한 방향

처음엔, 해당 노드에서 피자를 먹냐 안 먹냐를 정하면 되겠다 생각해

자료구조를 만들고 2차원 dp를 만들었지만

코드가 난잡해져서 잘못된 접근이란걸 알았다.

 

 

다시 생각한 방향

출발지와 도착지가 정해져있단 점을 이용해 거꾸로 풀어봤다.

예시 1을 적당한 수로 바꿨을 때의 각 노드에서 얻을 수 있는 최대 만족도는 다음과 같다.

 

여기서 추측할 수 있는 것은

지금까지 먹어온 피자를 1 / 2^(k-1) 씩만 먹었다고 가정할 땐, 현재 dp에서 2를 나눠주면 끝이다.

 

예를 들자면, 아래 그림에서 노드 2까지 갔을 때의 피자를 1 / 2^(k-1) 씩 먹어왔다고 가정하면 식은 다음과 같다.

노드 2 까지 오면서 피자를 1 / 2^(k-1) 씩 먹음

그다음 노드 3까지 갔을 때 피자를 1 / 2^(k-1) 씩 먹어왔다고 가정한 식이다.

 

노드 3 까지 오면서 피자를 1 / 2^(k-1) 씩 먹음

 

 

 

그렇다면 점화식은 이렇게 짜볼 수 있다.

 

dp[e] = max(dp[e], dp[s])

dp[e] = max(dp[e], smile[e] + dp[s] / 2) // smile은 만족도

 

여기서 s는 e의 자식이다.

노드 4에서 2로 간다 할 때, s는 4, e는 2이다.

 

코드는 접어놨다.

import java.io.*;
import java.util.*;

class Main {

    static int N, M;
    static int[] rank;
    static double[] smiles, dp;
    static ArrayList<Integer>[] graph;
    static StringBuilder answer = new StringBuilder();

    public static void main(String[] args) throws Exception {
        input();
        solve();
        print();
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        dp = new double[N];
        graph = new ArrayList[N];
        rank = new int[N];
        smiles = new double[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            smiles[i] = Double.parseDouble(st.nextToken());
            graph[i] = new ArrayList<>();
        }

        int s, e;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            s = Integer.parseInt(st.nextToken());
            e = Integer.parseInt(st.nextToken());
            graph[e].add(s);
            rank[s]++;
        }
    }

    private static void solve() {
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            if(rank[i] == 0) {
                dp[i] = smiles[i];
                q.add(i);
            }
        }

        while (!q.isEmpty()) {
            int current = q.poll();
            for (int next : graph[current]) {
                dp[next] = Math.max(dp[next], dp[current]);
                dp[next] = Math.max(dp[next], smiles[next] + dp[current] / 2);
                if(--rank[next] == 0)
                    q.add(next);
            }
        }

        System.out.printf("%.8f\n", dp[0]);
    }

    private static void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(answer.toString());
        bw.flush();
    }
}