글 읽기 - 채점은 100%까지 올라가는데 틀립니다.

letsgo90 6년 전 0

기본적으로 가장가까운공통조상찾기 로직을 활용했습니다.

leafNode가 2개 이상일 경우 그 둘을 폈을 때 가장 긴 지름이 되기 때문에

두 leafNode의 연결점인 공통조상까지의 거리를 합산하는 방식으로 했습니다.

조건) 노드가 1개 이상, leafNode가 2개 이상인 경우

: leafNode 끼리 연결되는 지점 (가장가까운공통조상) 까지의 cost를 합산하여 출력

예외 1) n =1 로 노드가 한개만 들어오는 경우

: 0 출력

예외2) 노드가 1개 이상, leafNode가 하나인 일자형 트리의 경우

: 일직선 상의 cost를 다 더해서 출력

위 부분은 주석으로 표기해놨습니다.

채점은 100%까지 올라가는데, 마지막에 틀렸습니다. 가 떠서 반례를 찾으려하는데 잘 보이지 않아

고수님들의 도움이 필요한 상황입니다.

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

public class Main {
	static int n ;
	static int[] myParent;
	static int[] upperCost;
	static ArrayList<Integer>leafNodes;
	static int[] depth;
	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());
		
		//1. root만 있을 경우 0 출력
		if(n==1){
			System.out.println(0);
			return;
		}
		
		myParent = new int[n+1];
		upperCost = new int[n+1];
		depth = new int[n+1];
		boolean[] isNotLeaf = new boolean[n+1];
		depth[1] = 0;
		
		for (int i = 0; i < n-1; i++) {
			st = new StringTokenizer(br.readLine());
			int parent = Integer.parseInt(st.nextToken());
			int child = Integer.parseInt(st.nextToken());
			int point = Integer.parseInt(st.nextToken());
			
			isNotLeaf[parent] = true;
			
			myParent[child] = parent;
			upperCost[child] = point;
			depth[child] = depth[parent]+1;
			
		}
		
		//2. 리프노드만 뽑아내기 
		leafNodes = new ArrayList<>();
		for (int i = 1; i <=n; i++) {
			if(!isNotLeaf[i]) leafNodes.add(i);
		}
		
		//3. leaf Node가 1개인 일자형 트리일 경우, 모든 거리를 더해서 출력
		if(leafNodes.size()==1){
			System.out.println(getOneLineCost());
			return;
		}
		
		//4. leaf Node가 2개 이상인 경우, leaf Node 간의 거리를 구해서 Max를 갱신
		int max = 0;
		for (int i = 0; i < leafNodes.size(); i++) {
			for (int j = i+1; j < leafNodes.size(); j++) {
				max = Math.max(max, lca(leafNodes.get(i), leafNodes.get(j)));
			}
		}
		System.out.println(max);
		
	}
	private static int getOneLineCost() {
		int sum = 0;
		for (int i = 1; i <=n; i++) {
			sum+=upperCost[i];
		}
		return sum;
	}

	//가장가까운공통조상 찾는 방식으로
	private static int lca(int a, int b) {
		int sum = 0;
		//1.두 노드의 depth 맞추기. depth를 올릴 때 cost를 더해준다.
		while(depth[a] > depth[b]){
			sum+=upperCost[a];
			a = myParent[a];
		}
		while(depth[b] > depth[a]){
			sum+=upperCost[b];
			b = myParent[b];
		}
		//2. 깊이가 같아졌으면, 같아질 때까지 (=공통 조상) depth 올라가기.
		while(a!=b){
			sum+=upperCost[a];
			sum+=upperCost[b];
			a=myParent[a];
			b=myParent[b];
		}
		return sum;
	}
}

letsgo90 6년 전 0

해결했습니다.

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

문제

문제

출처

ICPC

채점은 100%까지 올라가는데 틀립니다.

letsgo90 6년 전 0

letsgo90 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말