PS 일지

4/11 BOJ 24136 - 冊子の配布 (Distribution) Platinum 4 더보기 #greedy #dfs dfs를 $M$번 돌리며, 돌 때마다 가장 이득이 되는 리프 노드를 찾으면 된다. BOJ 15900 - 나무 탈출 Silver 1 더보기 #dfs 루트에서 모든 리프까지의 거리 합을 구하면 된다. BOJ 13164 - 행복 유치원 Gold 5 더보기 #greedy #sorting 인접한 두 원소의 차 중 큰 값을 $N-K$개 더하면 된다. BOJ 22104 - Три ладьи Gold 3 더보기 #case_work 주어진 판에서 나올 수 있는 서로 다른 경우의 수는 6가지밖에 없다. BOJ 11000 - 강의실 배정 Gold 5 더보기 #sweeping #priority_queue 우선..

너무 오래 쉰 것 같다. 종강을 하고도 PS는 종종 했지만, 글 쓰는게 귀찮아서 방치하다가 4개월치나 밀려버렸다. 한 번에 쓰기에는 문제 수가 너무 많아서 4월부터 다시 시작하려 한다... 4/2 BOJ 4384 - 공평하게 팀 나누기 Gold 1 더보기 #knapsack #dp 모든 사람들의 몸무게 합은 $45\,000$ 이하이고, 사람의 수가 $100$명 이하이다. 따라서, 사람이 한 명씩 추가될 때마다 (몸무게 합, 사람 수)로 가능한 경우를 knapsack dp로 갱신해주면 된다. BOJ 1043 - 거짓말 Gold 4 더보기 #bfs 주어진 $M$개의 파티 정보로 양방향 그래프를 만들고, 진실을 아는 사람들을 시작점으로 한 뒤 bfs를 돌려주자. bfs 수행 중에 만나는 모든 사람들에게는 거짓말..