PS 일지

4/11BOJ 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/2BOJ 4384 - 공평하게 팀 나누기Gold 1더보기#knapsack #dp 모든 사람들의 몸무게 합은 $45\,000$ 이하이고, 사람의 수가 $100$명 이하이다.따라서, 사람이 한 명씩 추가될 때마다 (몸무게 합, 사람 수)로 가능한 경우를 knapsack dp로 갱신해주면 된다. BOJ 1043 - 거짓말Gold 4더보기#bfs 주어진 $M$개의 파티 정보로 양방향 그래프를 만들고, 진실을 아는 사람들을 시작점으로 한 뒤 bfs를 돌려주자.bfs 수행 중에 만나는 모든 사람들에게는 거짓말을 할 수 없다..