전체 글 썸네일형 리스트형 BOJ)8012 한동이는 영업사원! 문제:icpc.me/8012 한동이가 방문해야 할 도시를 x->y->z->w 순이라면 x->y의 거리와 y->z의 거리 z->w의 최소시간을 더해서 출력하는게 답이된다. 결국 N,M제한 때문에 거리를 logN의 시간복잡도에 해결을 해줘야하는데 우리는 주어진 그래프가 트리라는걸 이용하여 LCA를 통하여 계산해 줄수 있다. x와 y의 최단 거리는 결국 모든 간선의 가중치가 1이니까 깊이를 이용하여 dph[x]+dph[y]-2*dph[lca(x,y)] 로 계산할 수 있다. 이를 이용하여 답을 구해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#in.. 더보기 BOJ)1761 정점들의 거리 문제:icpc.me/1761 두 정점간의 최단거리를 매 쿼리마다 출력하는 문제이다. 우리가 기본적으로 알고 있는 그래프의 최단거리 알고리즘들은 시간복잡도 때문에 사용할 수가 없다. 하지만 우리는 이 그래프가 트리라는것을 이용하여 매 쿼리를 O(logN) 시간마다 처리해 줄 수있다. 우리는 lca를 이용하여 두 노드의 최단 거리를 계산할 것이다. lca전처리를 위해 dfs를 돌려줄 때 루트에서 부터 자기 자신까지의 거리를 dist배열에 저장해두면 두 노드의 X,Y 의최단 거리는 dist[X]+dist[Y]-2*dist[lca(X,Y)]로 정의 할 수있다. 이를 이용하여 매 쿼리를 logN시간에 처리해주면 된다. 12345678910111213141516171819202122232425262728293031.. 더보기 BOJ)2512 예산 문제:icpc.me/2512 최소중의 최대를 구하는 전형적인 파라메트릭 서치 문제이다. 다만 주의해야 할 건 모든 인풋 a[i]의 합이 m보다 작을 경우 a[i]중에 최댓값을 출력해줘야 하는 예외 케이스가 있다. 123456789101112131415161718192021222324252627282930313233343536#include #include typedef long long ll;using namespace std;ll n, a[10000], m, lo, hi, ma, s;int main() { scanf("%lld", &n); for (int i = 0; i = s) { printf("%lld\n", ma); return 0; } lo = 0; hi = 21000000000; while (.. 더보기