글 읽기 - 시간초과 이유를 모르겠습니다..

tpwls8122 5년 전 0

메모이제이션 처리를 했다고 생각하는데

아무리 봐도 아무리 고쳐도 시간초과가 뜨네요.

혹시 제가 놓친 부분이 있을까요 ;;

예시 입력에 대한 결과는

3 3 2 0 0 ( 인덱스 1,2,3,4,5 )의 해킹할수있는수 이렇게 나옵니다.

예시 출력처럼 1 2 도 나옵니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int N, M;
	static int[] store;
	static ArrayList<ArrayList<Integer>> list;

	public static void main(String[] args) 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());

		store = new int[N + 1];
		list = new ArrayList<ArrayList<Integer>>();
		for (int i = 0; i <= N; i++)
			list.add(new ArrayList<Integer>());

		for (int m = 0; m < M; m++) { // 인접 리스트에 신뢰관계 추가
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			list.get(b).add(a);
		}

		int max = -1;
		Arrays.fill(store, -1); // 메모 -1로 저장

		for (int i = 1; i <= N; i++) {
			max = Math.max(max, dfs(i));
		}

		StringBuilder sb = new StringBuilder();
		for (int i = 1; i <= N; i++)
			if (store[i] == max)
				sb.append(i + " ");

		System.out.println(sb.toString()); // 답 출력

		br.close();
	}

	static int dfs(int node) {
		if (store[node] != -1) // 이미 확인한 것이면 바로 리턴
			return store[node];

		store[node] = list.get(node).size(); // 신뢰관계있는 노드만큼 추가

		for (int next : list.get(node)) {
			store[node] += dfs(next); // 신뢰관계에 있는 노드에서 퍼질수있는 만큼 추가
		}
		return store[node];
	}
}

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

문제

문제

출처

ICPC

시간초과 이유를 모르겠습니다..

tpwls8122 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말