반응형 11438번1 백준 11438번 - LCA2 (C++) 문제 해결 방법 기존 LCA와 똑같이 풀이하되, 기존에는 공통 조상을 찾기 위하여 한칸한칸 전진하며 찾았지만, 데이터 범위가 늘어나 한칸한칸 전진하며 탐색하면 시간 초과가 나온다. 때문에 각 숫자별로 (2^0, 2^1, 2^2... 2^16)만큼 전진한 부모를 저장하여 2의 제곱수만큼 전진하며 탐색한다. 'Parents[i][j] = 2^j만큼 떨어진 i의 부모'이다. 2의 제곱수만큼 전진한 부모를 아는 방법은, "Parents[i][j + 1] = Parents[Parents[i][j]][j]"를 해주면 된다. 풀이를 하자면,나의 2^2+1(8칸)만큼 떨어진 부모는 나의 2^2(4칸)만큼 떨어진 부모의 2^2(4칸)만큼 떨어진 부모다. 즉 8칸=4칸+4칸, 2^3=2^2+2^2인것과 같은 원리다. (1.. 2021. 10. 2. 이전 1 다음 반응형
