Problem Solving (27) 썸네일형 리스트형 BOJ 99등 달성 나름 큰 목표였던 'BOJ 랭킹 1페이지에 이름 올리기'를 드디어 성공했다. 와! [BOJ 13982] Shopping 13982번: Shopping For each of the q customers, print, on a single line, a single integer indicating the remaining amount of money after shopping. www.acmicpc.net 2000번째 문제로 뭘 풀까 고민하다가 IBory님께 추천을 받았다. 깔끔하고 재밌는 문제였다. 풀이 쉽게 할 수 있는 관찰은 현재 가지고 있는 돈보다 가격이 높은 구간은 모두 통과할 수 있다는 것이다. 현재 가지고 있는 돈이 바뀌는 부분에 주목해보자. $v$ $\%$ $a_i = w$ 에서 $w$ 는 $\frac{v}{2}$ 보다 작거나 같다. 이는 $a_i$ 의 범위에 따라 케이스 분류를 해봄으로써 보일 수 있다. 따.. 와 2000문제! First Solve 3개 퍼솔을 처음 시도해보았다. 쫄려서 쉬워보이는 것들만 찍먹함. ㅎㅎ [BOJ 1167] 트리의 지름 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 널리(?) 알려진 것과 달리 dfs 한 번으로 해결할 수 있다. 사실 그 방법을 몰라서 이렇게 풀었다. 풀이 임의의 루트를 하나 잡고 트리를 구축했다고 생각하자. 트리의 지름을 만드는 두 노드의 공통 조상은 트리 위의 노드 중 하나이기 때문에, 모든 노드에 대하여 그 노드를 공통 조상으로 하는 두 노드의 최대 거리를 시도해보면 된다. 이를 위해 필요한 정보는 각 서브 트리의 최대 깊이와 여러 서브 트리 중 첫 번째와 두 번째로 깊은 깊이이고, 이.. 이전 1 2 3 4 ··· 6 다음
