본문 바로가기

Problem Solving

(26)
[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 한 번으로 해결할 수 있다. 사실 그 방법을 몰라서 이렇게 풀었다. 풀이 임의의 루트를 하나 잡고 트리를 구축했다고 생각하자. 트리의 지름을 만드는 두 노드의 공통 조상은 트리 위의 노드 중 하나이기 때문에, 모든 노드에 대하여 그 노드를 공통 조상으로 하는 두 노드의 최대 거리를 시도해보면 된다. 이를 위해 필요한 정보는 각 서브 트리의 최대 깊이와 여러 서브 트리 중 첫 번째와 두 번째로 깊은 깊이이고, 이..
[BOJ 12784] 인하니카 공화국 12784번: 인하니카 공화국 인하니카 공화국은 1번~ N번까지 N개의 섬으로 이루어진 나라이다. 이 나라에서는 섬 간의 왕래가 매우 어려웠지만, 위대한 다리 설계자 ‘진’이 두 섬을 연결하는 다리를 최소한의 개수로 만들 www.acmicpc.net 이 문제와 정확히 일치하는 문제를 GCC 출제 큐에 push하고 나서 반나절 뒤에 트리 디피 문제를 찾아 풀다가 우연히 발견했다. AC를 받기 전까지 제발 내 착각이기를 빌었다.. 흔한 유형이라 비슷한 문제가 있을 거라고 생각하기는 했지만, 아쉬운 것은 어쩔 수 없다. 풀이 루트와 리프를 연결하는 경로가 없도록 만들 때, 자르는 간선의 가중치의 합이 최소가 되게 하는 문제다. 이는 dfs를 돌면서 트리의 정점에 대한 dp를 해결하면 된다. $dp[u]=\su..