전체 글 썸네일형 리스트형 BOJ)14950 정복자 문제:icpc.me/14950모든 도시를 점거하는데 필요한 최소 비용을 출력하는 문제이다.단 도시를 점거 해 나갈 때 마다 일정 비용이 추가 되었는 데 이것에 포커스를 맞추면 문제가 어려워 질 수 있다.조금 생각을 해보면 결국 모든 도시를 점거해야하기 때문에 MST를 만들어주면 비용을 커버할 수 있는 걸 알 수 있다.이미 MST를 구상하였다면 이에 이용 된 간선은 n-1개로 고정일 것이고, 이는 모든 도시를 점거하는데 필요한 간선의 최소 개수이기도 하기 때문에(1~n-1 까지의 합) x t가 증가하는 비용으로 고정된다.123456789101112131415161718192021222324252627282930313233343536373839#include #include #include using nam.. 더보기 BOJ)15271 친구 팰린드롬2 문제: icpc.me/15271남자와 여자에 대한 이분 그래프가 형성되므로 이분 매칭으로 최대로 세울 수 있는 친구 수를 구해줄 수 있다.1234567891011121314151617181920212223242526272829303132333435363738394041424344#include #include #include #include using namespace std;int n, m, visited[222], b[222];vector vt;int dfs(int here) { if (visited[here])return false; visited[here] = true; for (auto next : vt[here]) { if (!b[next] || dfs(b[next])) { b[next] = .. 더보기 BOJ)15270 친구 팰린드롬 문제: icpc.me/15270 명시 된 N의 범위가 작으므로 상태DP를 이용하여 해결할 수 있다.dp[state][pos] = state(이미 친구가 된 사람들의 상태를 표현)이고 pos번째 까지 친구 관계를 봤을 때 춤을 추는 인원의 최댓값12345678910111213141516171819202122232425262728#include #include #include using namespace std;int dp[1 더보기 이전 1 ··· 4 5 6 7 8 9 10 ··· 118 다음