devlog

출처 : https://www.acmicpc.net/problem/18234 풀이 방법pi는 wi보다 항상 크다.라는 조건에 의해 그리디로 풀이할 수 있음을 파악했다.pi는 당근을 뽑지 않으면 계속해서 누적되다가 해당 당근을 뽑게 된다면 누적된 pi와 wi만큼 맛을 얻을 수 있다.이를 통해 T일 전까지 가장 큰 pi를 계속 누적을 하다 마지막에 뽑는 것이 가장 많은 맛을 얻을 수 있다는 것을 알 수 있다. 또한 pi는 wi보다 항상 크다라는 조건에 의해, 만약 T가 6이고 당근이 3종류라면 6, 5, 4일 차에만 당근을 뽑아 먹고, 1, 2, 3일 차에는 당근을 안 뽑아 먹는 것이 더 크다는 조건을 알 수 있다. (만약 뽑게 된다면, wi가 중간에 포함되어야 하기 때문에 안 뽑고 Pi만큼 얻는게 더 좋다..

출처 : https://www.acmicpc.net/problem/17398 풀이 방법풀이의 방법만 안다면 구현은 간단한 문제였다. 간선을 하나씩 끊어 가면서 이때 나누어진 두 집합의 노드의 수를 계산하는 문제이다.만약 간선을 끊을 때마다, 끊어진 두 노드에서 bfs 또는 dfs를 수행해서 각 집합의 노드의 수를 계산하게 된다면 시간 복잡도가 초과된다.그렇게 때문에 nlogn 이하의 시간 복잡도를 가지는 알고리즘을 생각해 내야 했다. 지금 까지 공부하며 시간 복잡도를 줄였던 방법에 대해 생각해 보았다. 1. 노드기준이 아닌 엣지 기준으로 생각해 보기2. 방향 간선에선 간선의 방향을 바꾸어 보기3. 순서를 역으로 생각해 보기 등등 생각이 났지만, 이 문제에 적용할 수 있는 방법은 역으로 생각하기였다. 1...