14267번 - 회사 문화 1
일반적으로 정형화된 트리로 풀면 O(NM)으로 시간초과가 발생하는데 이걸 O(N+M)으로 풀 수 있다는게 참..
힌트를 참고하긴 했지만 어려운 방식도 아니고 참신하달까.. 어떻게 저렇게 시간복잡도를 줄일 생각을 할 수 있는지..
이런건 직관적으로 보는 힘을 길러야 하는지, 경험이 쌓이면 보일 수 있는건지, 아님 제가 단순히 부족한건지 아직 잘 모르겠습니다.
푸신분들은 다들 어떻게 접근하셨나요?
p.s.
제가 참고한 O(N+M)방식은 칭찬 수치에 대한 누적합 방식이었는데 다른 방식도 있는지 궁금합니다.
#누적 합 태그와 #트리에서의 다이나믹 프로그래밍 태그를 어느 정도 풀어봤다면 전형적인 문제에 가깝습니다. '경험이 쌓이면 보이는' 쪽에 가깝다는 것이죠. 물론 트리 DP라는 유형 자체가 골드 하위 이하에서는 거의 등장하지 않는 유형이기 때문에 많이 접해보기 어려운 것도 사실입니다. 비슷하거나 좀더 심화된 문제는 백준 단계별로 풀어보기 38단계를 참고하시면 좋을 것 같습니다.
@oh040411 님 답변 감사합니다.
아직 문제를 푼 수와 경험이 부족하지만 그럼에도 조금씩 난이도를 올리면서 문제를 접할 때마다 와.. 어떻게? 이런 반응만 나와서 고민이 되었네요.
좋은 조언 감사드립니다 ㅎㅎ
이 방식이 누적합이나 트리DP의 일종인지 모르겠지만 아이디어 공유해봅니다
각 노드에 내리칭찬이 아닌 첫 칭찬만 더해놓고 재귀 Bottom-up 방식으로 하위노드에서 상위노드의 점수를 요구해서 더하고, 상위노드는 또 상위노드의 점수를 요구해서 더하고, ..., 최상위인 사장은 0을 반환하도록 했습니다
두번 호출될 경우를 대비해서 메모이제이션도 했는데 생각해보니 그냥 DP네요
댓글을 작성하려면 로그인해야 합니다.
sam020329 1년 전
일반적으로 정형화된 트리로 풀면 O(NM)으로 시간초과가 발생하는데 이걸 O(N+M)으로 풀 수 있다는게 참..
힌트를 참고하긴 했지만 어려운 방식도 아니고 참신하달까.. 어떻게 저렇게 시간복잡도를 줄일 생각을 할 수 있는지..
이런건 직관적으로 보는 힘을 길러야 하는지, 경험이 쌓이면 보일 수 있는건지, 아님 제가 단순히 부족한건지 아직 잘 모르겠습니다.
푸신분들은 다들 어떻게 접근하셨나요?
p.s.
제가 참고한 O(N+M)방식은 칭찬 수치에 대한 누적합 방식이었는데 다른 방식도 있는지 궁금합니다.