취미로PS하는사람

최근에 PS를 다시 하면서 뭘 풀어야 할지 모르겠다는 생각이 들었다. 둘러보다가 고등학교 친구가 만든 인생추천셋이 있길래 차근차근 풀어보려고 한다. https://dsstar.tistory.com/53 Journey to TST 문제 셋 공유 BOJ 그룹(https://www.acmicpc.net/group/16794)에서 2주 동안 총 44(+2) 문제의 연습 셋을 공유했다. 11일 간 매일 선발고사 난이도에 맞추어 4문제씩 셋을 만들었다. 모든 문제에서 얻어갈 내용이 있으며, 내 9 dsstar.tistory.com 내가 푼 순서대로 리뷰하려고 한다. 때문에 세터의 의도와는 다르게 대략 난이도 순이니 이 부분에 있어서 스포일러를 원치 않는다면 문제를 풀고 오기를 바란다. 약 4.5일간 푼 것 같다. ..

https://www.acmicpc.net/problem/8128 나의 접근 방식은 이러하다. 1. 리프 노드 사이로만 길을 놔야 한다. 이는 너무 당연하다. 2. 가장 점이 많이 포함되도록 길을 놓았을 때 그 점들의 집합은 끊어져 있지 않다. 만약 끊어져있다면 한 쪽의 한 경로와 다른 쪽의 한 경로의 한 끝점을 맞바꾸면 떨어진 두 컴포넌트 사이의 모든 정점도 포함되기 때문에 언제나 최적의 상태에서 위 조건을 만족하지 않을 수 없다는 것을 알 수 있다. 위 두 조건으로부터 최적 정점 집합은 리프 노드가 총 2*k개인 서브그래프라는 것을 알 수 있다. 이 때 포함된 정점 개수를 최대화 해야 한다. 3. 최적 점의 집합은 트리의 지름을 포함한다. 몇 번 그려보면 왠지 그럴 것 같다는 느낌을 받을 수 있다. ..

https://www.acmicpc.net/problem/8125 간선을 반대로 생각하고 위상정렬하면서 사이클이 있으면 zawsze이니까 그 사이클 임의의 한 점으로부터 dfs하여 모든 점을 색칠하고, 사이클이 없다면 경우의 수를 dp로 구해주면 된다. 쉬운 문젠데 메모리 제한이랑 코딩 미스 때문에 상당히 애를 먹었다... 코드 더보기 #include #define fi first #define se second #define eb emplace_back #define em emplace #define all(v) v.begin(), v.end() using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; const int..