백준 2820 자동차 공장 혼내주기
내 접근법은 트리를 만들고 월급을 출력해야 할 때 해당 노드부터 root 까지 올라가는 path를 저장하고 그 path의 역순으로 update를 해서 propagated 값을 출력하는 방법이었는데 TLE를 받았다. 시초를 받고 생각해보니 트리가 skewed tree일 때 매번 경로를 찾기 위해 O(N)이 걸리기 때문에 그런 것 같다. 도저히 풀이가 안떠올라서 검색하다가 ANZ님의 블로그를 보고 이해했다. range가 없으니 dfs로 해당 노드의 구간을 만들어서 쿼리를 날린다... 구현하고도 dfs로 재정의된 노드 순서를 적용 안해서 또 한참 헤맸다. 세그 문제들은 디버깅이 어렵다. 결국 lazy에 구간 재정의만 해주면 되는 문제였고, 그걸 검색해서 알고도 왜 이렇게 헤맸을까........ 세상에 똑똑한 ..
혼내주기
2021. 7. 23. 10:50