글 읽기 - java 시간초과 질문드립니다 ㅜㅜ

ckddn1224 3년 전 0

34퍼쯤 시간초과가 나오는데 왜 시간초과가 나오는지를 모르겠습니다..

고수님들 도와주세요 ㅠ

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int n;
    static int[] arr;
    static ArrayList<ArrayList<Integer>> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        arr = new int[n + 1];

        for (int i = 0; i <= n; i++) {
            list.add(new ArrayList<>());
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list.get(a).add(b);
            list.get(b).add(a);
        }

        int result = Math.max(dp(1, -1, true) + arr[1]
                , dp(1, -1, false));

        bw.write(String.valueOf(result));
        bw.close();
        br.close();
    }

    static int dp(int cur, int parent, boolean flag) {
        int ans = 0;

        for (int child : list.get(cur)) {
            if (child != parent) {
                if (flag) {
                    ans += dp(child, cur, false);
                } else {
                    ans += Math.max(dp(child, cur, true) + arr[child]
                            , dp(child, cur, false));
                }
            }
        }
        return ans;
    }
}

djm03178 3년 전 2

함수 이름을 dp라고 지으셨지만 실제로는 dp를 수행하지 않고 그냥 탐색을 하고 있습니다. 각 호출에서 구한 답을 메모이제이션을 해보세요.

ckddn1224 3년 전 0

재귀로된 함수가 끝까지 내려가면 차례차례 종료되면서 값이 갱신되니까 따로 배열에 저장하지 않아도 된다 생각했습니다

감사합니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

java 시간초과 질문드립니다 ㅜㅜ

ckddn1224 3년 전 0

djm03178 3년 전 2

ckddn1224 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말