G14267. 회사 문화 1

문제

제출 코드

• 사용 알고리즘 : 트리, DP?

단순하게 생각하고 DFS로 자식노드까지 누적합을 계산하기엔, 노드의 최대개수가 커서 시간초과가 날 수 있어보였다. 문제에서 친절하게 상위노드가 숫자가 작음을 언급한 점이 해결점이 되었다.

각 노드별로 자식노드들의 정보를 저장해둔 뒤에, 상위노드부터 순차적으로 바로 하위의 자식노드들에게만 본인이 받은 칭찬을 더해주면 된다. 이 과정을 거치면, 자식노드의 하위노드들까지 중복연산을 할 필요가 없어진다.

번외) 문제명을 보면 알겠지만, 이 문제는 조건을 바꾼 다른 문제들이 존재한다.

2부터 급격히 플레티넘으로 난이도가 상승하기에 궁금해서 시도했는데, 시간초과로 제대로 깨져버렸다.. 다음에 다시 도전해봐야겠다.

package gold;

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

public class G14267_companyCulture {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		List<Integer>[] childs = new List[N+1];
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++) {
			childs[i] = new ArrayList<Integer>();
			int parent = Integer.parseInt(st.nextToken());
			if(i>1) childs[parent].add(i);
		}

		int[] praise = new int[N+1];
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int idx = Integer.parseInt(st.nextToken());
			praise[idx] += Integer.parseInt(st.nextToken());
		}

		StringBuilder sb = new StringBuilder();
		for(int i=1; i<=N; i++) {
			for(int child : childs[i]) praise[child] += praise[i];
			sb.append(praise[i]+(i<N ? " " : "\n"));
		}

		System.out.println(sb);
	}

}