문제를 잘 읽어보면 한가지 알고리즘이 떠오른다 LCA!!! 간만에 떠올라서 잠깐 다시 공부하고 오랜만에 만들어봤다! 먼저 이 문제는 1이 루트고 bfs로 나머지 정점들에 순서대로 계속 가기 때문에 정점 2개씩 잡으며 lca를 구해서 lca까지의 거리를 더해가면 답을 구할 수 있다 lca만 알면 쉽게 풀 수 있는 문제다! 근데 더 어려운건 swea에서 스택메모리가 1메가라그런지 dfs로 깊이를 매기니 런타임 에러가 났다;; 대체 어디가 틀린지 몰랐는데 이게 틀렸었다;; bfs로 바꿔서 깊이를 찾았다!! 함수였던건 다 메인으로 넣어버렸다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 ..
트라이 기본 문제다. 트라이 짜는법을 마지막으로 정적으로 배웠기 때문에 정적트라이를 이용했다! 문제를 푸는 방법은 간단하다 트라이를 만들고 cnt배열을 만들어서 지나가는 정점마다 cnt를 올려주면 된다 그럼 내가 어떤 지점에서 시작한다고 할 때 그 수만큼 cnt가 올라갈 것 이다 근데 문제는 초기화가..! 문제였다 정적으로 잡기 때문에 노드의 수를 미리 max로 두고 시작한다 여기서는 100000개의 쿼리 X 10자리수 X 알파벳 26개 다 근데 바보같이 초기화 하는 부분에서 max 크기만큼 모든배열을 계속 초기화했다 시간초과가 정확히 30번 났다 혹시 오타가 났나 계속 다시 짰는데 문제는 초기화였다 생각해보면 초기화는 내가 사용한 정점까지만 해주면 된다 trie_cnt에 저장해놨기 때문에 딱 이만큼만 ..