hiasince12   5년 전

LCA2 를 풀었는데 자꾸 출력초과라고 뜹니다....

문제에서 요구하는 답 이외에 출력하지 않는데 왜 출력초과가 자꾸 나는 걸까요?

정답코드와 비교해도 큰 차이가 없는 듯한데 너무 답답하네요 도와주세요!

djm03178   5년 전

몆가지 문제가 있습니다.

1. P[a][x]는 a의 2^x번째 조상이니까, P[P[a][x - 1]][x - 1]이 되어야 하는데, 지금 코드는 2^(x-1)번째 조상의 바로 부모로 하고 있습니다.

2. 그런데 이 코드를 그대로 저렇게 고치면, P[a][x - 1]의 2^(x-1)번째 조상이 아직 결정나지 않았을 수 있는 문제가 발생합니다. 그래서 이 과정은 지금 같은 반복문으로 처리가 불가능하고, 트리를 구성하는 과정에서 부모 노드부터 차례대로 수행하도록 해야 합니다.

출력 초과가 나는 건, 정답에는 작은 수를 많이 출력해야 하는데 큰 수를 많이 출력해서 출력이 너무 많았던 것으로 추측합니다.

hiasince12   5년 전

아 바로 위 부모를 조상으로 하는게 아니라 2^x만큼 조상으로 설정했던 부분을 깜빡했었습니다!!

해결했습니다 .감사합니다

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