[BOJ][JAVA] 14267번: 회사 문화 1

 

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

14267번: 회사 문화 1

 

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

public class Main {
	static List<Integer>[] t;
	static int[] p;
	static boolean[] v;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		t = new ArrayList[n + 1]; // idx=1은 사장이니까 -1들어감.
		// -1 1 2 3 4
		// 1은 사장이니 직속 상사가 없으므로 -1
		// 2는 직원, 사장이 직속상사.
		p = new int[n + 1];
		int sajang = sc.nextInt();
		for (int i = 1; i <= n; i++) {
			t[i] = new ArrayList<>();
		}
		for (int i = 2; i <= n; i++) {
			int sup = sc.nextInt(); // i번 직원의 상사가 tmp다.
			t[sup].add(i);
		}

		for (int i = 1; i <= m; i++) {
			int idx = sc.nextInt();
			int w = sc.nextInt();
			v = new boolean[n + 1];
			f(idx, w);
		}
		StringBuilder sb = new StringBuilder();
		for (int i = 1; i <= n; i++) {
			sb.append(p[i]).append(" ");
		}
		System.out.println(sb);
	}

	public static void f(int target, int appr) {
		v[target] = true; 
		if (p[target] == 0) {
			p[target] = appr;
		} else {
			p[target] += appr;
		}
		for (int i = 0; i < t[target].size(); i++) {
			int child = t[target].get(i);
			if(!v[child]) {
				f(child, appr);
			}
			 // 자식을 꺼내서, 걔도 넣어줌.
//			p[target] += appr; <- 이 방식이면 leaf 노드는 자식이 없어서 더해질 일이 없다..
		}
	}
}

 

 

---

오답노트(푸는 동안 사고과정 및 개선점)

시간 초과가 나는 코드다. 입력이 10만인데 for문안에 for를 돌리는 재귀함수를 넣어버렸으니 당연히 시간초과가 난다..

칭찬을 계산할 배열을 따로 빼서 관리해야 o(n)으로 가능하다...!

visited배열이 필요가 없었던 문제!

 

---

정답코드

public class Main {
	static List<Integer>[] t;
	static int[] p;
	static int[] like;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		t = new ArrayList[n + 1]; // idx=1은 사장이니까 -1들어감.
		// -1 1 2 3 4
		// 1은 사장이니 직속 상사가 없으므로 -1
		// 2는 직원, 사장이 직속상사.
		p = new int[n + 1];
		like = new int[n + 1];
		int sajang = sc.nextInt();
		for (int i = 1; i <= n; i++) {
			t[i] = new ArrayList<>();
		}
		for (int i = 2; i <= n; i++) {
			int sup = sc.nextInt(); // i번 직원의 상사가 tmp다.
			t[sup].add(i);
		}

		for (int i = 1; i <= m; i++) {
			int idx = sc.nextInt();
			int w = sc.nextInt();
			like[idx] += w;
		}

		f(1);

		StringBuilder sb = new StringBuilder();
		for (int i = 1; i <= n; i++) {
			sb.append(like[i]).append(" ");
		}
		System.out.println(sb);
	}

	public static void f(int target) {
		for (int i = 0; i < t[target].size(); i++) {
			int child = t[target].get(i);
			like[child] += like[target];
			f(child);
		}
	}
}

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요! 로그인 안해도 됩니다 ^_^