백준 14267 회사 문화 1 [JAVA]

백준 14267 회사 문화 1 [JAVA]

728x90

solved.ac = 골드 4

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

1. 접근

먼저 문제를 살펴보겠습니다.

문제 속 지문을 살펴보면 요구사항은 두 가지로 보입니다.

특정 직원을 칭찬하면 칭찬받은 직원의 부하 직원들도 같이 칭찬받는다.

칭찬에는 수치가 있으며 모든 칭찬이 끝나면 모든 직원들에 대해 누적 칭찬 치를 출력한다.

예제 입력을 예시로 각 직원을 노드로, 상하 관계를 부모 자식 관계로 나타낸 트리로 보면 다음과 같습니다.

그림을 보며 위 요구사항을 다시 정리하면

특정 직원을 칭찬하면 칭찬받은 직원의 부하 직원들도 같이 칭찬받는다.

=> 특정 노드에 값을 더하면 자식 노드의 값도 더해진다!

칭찬에는 수치가 있으며 모든 칭찬이 끝나면 모든 직원들에 대해 누적 칭찬치를 출력한다.

=> 단순 이동거리가 아닌 특정 숫자가 주어지며 모든 노드의 값을 출력해야 한다!

즉, 모든 노드의 칭찬받은 정도를 출력해야 하니 당연히 모든 노드를 다 확인해야 하는데

입력 제한사항을 살펴보면 칭찬의 정도는 최대 1,000, 칭찬의 회수 및 직원의 수는 최대 100,000입니다.

즉, 입력의 최댓값은 칭찬의 수치 최대값 * 직원 최대의 수 = 1,000 * 100,000 = 100,000,000로 Integer를 사용해도 되며

매 칭찬마다 자식 노드를 탐색하면 최악의 경우 m²으로 약 100억인데 이는 시간제한 2초 안에 풀 수 없습니다.

따라서 DP를 이용해 최초 입력값에서 각 노드에 칭찬 값을 세팅한 후 본인의 칭찬 수치를 자식의 칭찬 수치에 더하는 방법으로 한 번의 탐색으로 끝내야 합니다.

캬! 훈훈하니 보기 좋다!

이후 카운트한 배열을 1번 직원부터 순서대로 출력하면 정답입니다.

2. 풀이

변수 세팅

static int N, M; static ArrayList[] tree; static int[] cnt; public static void main(String[] args) throws IOException { st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); st = new StringTokenizer(br.readLine()); tree = new ArrayList[N + 1]; for (int i = 1; i <= N; i++) tree[i] = new ArrayList<>(); for (int i = 1; i <= N; i++) { int x = Integer.parseInt(st.nextToken()); if (x == -1) continue; tree[x].add(i); // 밑으로만 뻗어나가니 반대의 경우는 add하지 않는다. } cnt = new int[N + 1]; for (int i = 1; i <= M; i++) { st = new StringTokenizer(br.readLine()); // x = 칭찬받은 번호 , y = 칭찬 수치 int x = Integer.parseInt(st.nextToken()), y = Integer.parseInt(st.nextToken()); cnt[x] += y; } solution(); }

탐색 및 정답 출력

static void solution() { DFS(1); for (int i = 1; i <= N; i++) sb.append(cnt[i]).append(' '); System.out.println(sb.toString()); }

탐색

static void DFS(int x) { for (int y : tree[x]) { cnt[y] += cnt[x]; // 부하 칭찬 누적치에 본인 칭찬 누적치를 더한다! DFS(y); } }

3. 전체 코드

728x90

from http://dhbang.tistory.com/42 by ccl(A) rewrite - 2021-12-27 16:27:40