boi (2) 썸네일형 리스트형 백준 3397번 Division Expression https://www.acmicpc.net/problem/3397 괄호가 없는 x1/x2/x3/ ... /xk를 생각해 보자. 분자에는 x1 하나만 있고 다른 수는 전부 분모가 된다.괄호를 이용한 기본적인 식 (x1/x2) / (x3/x4)를 보면 나눗셈의 앞부분에는 영향이 없지만 나눗셈 뒤에 오는 괄호 안의 분수는 역수로 취해져 분자와 분모가 바뀌게 된다. 괄호가 없을때와 비교하면 x3는 그대로 나누어지지만 x4는 곱해지게 된다.우선 괄호를 어디에 두더라도 x1은 분자, x2는 분모에 위치한다는 것을 알 수 있다. 정수를 만드려면 분모의 인수가 적을수록 유리함으로 분모에 곱해지는 수는 최소화 해야한다. x1/(x2/x3/x4/.../xk)를 하면 (x1*x3*x4*...*xk) / x2가 되어 유클리드.. 백준 22199번 Cat in a tree https://codeforces.com/blog/entry/134665코드포스 블로그를 둘러보다 트리DP에서 노드의 정보를 스몰 투 라지로 합치는 검은돌 트릭이 서브트리의 크기가 아닌 최대 깊이에 비례하는경우 상당히 빨라진다는 글을 보았다. qwerasdfzxcl 님이 말하기로는 시간복잡도가 무려 O(N)이 나온다고 하였다. 최근 팀연습에 나온 요코하마 2023 J번이나(이건 정해가 HLD이다! 검은돌 트릭을 쓰면 1초면 충분하다!) 이번 카이스트 Mock L번 등 최근 자주 사용되는 유형인것 같아 여러 경우에 따른 시간복잡도를 알아두면 꽤나 도움이 될것같다. https://www.acmicpc.net/problem/22199소개된 연습문제 하나가 백준에 있어 풀어보았다. 내가 짠 코드는 deque가 .. 이전 1 다음