백준 #1135 #Java

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

처음에 이 문제를 접했을 때
자식 노드들에게 전화하는 모든 방법을 조합으로 만들고 메모이제이션해서
최소로 걸리는 시간을 리턴하는 방식으로 풀었는데 메모리초과가 났다.

이전 문제에서도 봤다시피 2^30만 해도 10억이 넘기 때문에 조합으로 풀 수 없던 것이다. (0 < n <= 50)

이 문제는 자식노드에서 걸리는 시간들을 내림차순으로 정렬하고
순서대로 +1, +2, +3,,, 한 값중 가장 큰 값을 뽑아내면 된다.

자식들 중 가장 오래 걸린시간 = t1
그 다음으로 오래 걸린시간 = t2
...
ans = max(t1+1, t2+2, t3+3, t4+4, ,,,)

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

public class Main {
	
	static int n;
	static ArrayList<Integer>[] childOf;
	static boolean[] used;
	static int[] dp;
	static int[] array;
	
	public static void main(String[] args) throws Exception{
			
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		st.nextToken();
		childOf = new ArrayList[n];
		for (int i=0; i<n; i++) childOf[i] = new ArrayList<>();
		for (int i=1; i<n; i++) childOf[Integer.parseInt(st.nextToken())].add(i);
		
		dp = new int[n];
		used = new boolean[n];
		array = new int[n];
		Arrays.fill(dp, -1);
		System.out.print(makeAns(0));
	}
	
	public static int makeAns(int now) {
		
		ArrayList<Integer> list = new ArrayList<>();
		
		for (int num: childOf[now]) {
			list.add(makeAns(num));
		}
		
		int result = 0;
		Collections.sort(list, Collections.reverseOrder());
		for (int i=0; i<childOf[now].size(); i++) {
			result = Math.max(result, i + 1 + list.get(i));
		}
		return result;
	}
}