본문 바로가기

Problem Solving

 (135)
[ BOJ 백준 16562번 - 친구비 ] 해설 및 코드 https://www.acmicpc.net/problem/16562 목적 친구의 친구도 친구라는 규칙(?)에 따라 모든 학생과 친구가 되기 위해 필요한 최소 비용을 구하자. 접근법 1. 분리집합을 이용한다. 다만, 비용이 적은 학생을 루트 노드로 하는 집합을 형성하자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 #include #define f(i,l,r) for(int i=l;i n >> m >> k; f(i, 1, n) { cin >> cost[i]; a[i] = i; } while (m--) ..
[ BOJ 백준 1976번 - 여행 가자 ] 해설 및 코드 https://www.acmicpc.net/problem/1976 목적 도시가 서로 연결되어 있는지 구하자. 접근법 1. 분리집합 기본 문제. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include #define f(i,l,r) for(int i=l;i> tmp; int r = root(tmp); while (--m) { cin >> tmp; if (r != root(tmp)) { while (--m)cin >> tmp; return false; } } return true; } int main() { ios_base::sync_with_st..
[ BOJ 백준 1717번 - 집합의 표현 ] 해설 및 코드 https://www.acmicpc.net/problem/1717 목적 a,b 두 원소가 포함된 집합을 합치거나, 하나의 집합에 포함되어 있는지 확인하자. 접근법 1. 분리집합 기본 문제이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #include #define f(i,l,r) for(int i=l;i> n >> m; f(i, 0, n + 1)a[i] = i; while (m--) { int c, a, b; cin >> c >> a >> b; if (c)cout
[ BOJ 백준 1351번 - 무한 수열 ] 해설 및 코드 https://www.acmicpc.net/problem/1351 목적 점화식을 풀어 An을 구하자. 접근법 1. An이 x*A0 꼴이 될 때까지 map에 넣고 반복하자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include #define f(i,l,r) for(int i=l;i>n>>p>>q; map m;m[n]=1; while(true){ map::iterator it=m.end(); if((--it)->first==0)break; m[it->first/p]+=it->second; m[it->first/q]+=it->second; m.erase(it); } cout
[ BOJ 백준 1269번 - 대칭 차집합 ] 해설 및 코드 https://www.acmicpc.net/problem/1269 목적 두 집합의 합집합에서 교집합을 빼자. 접근법 1. 두 집합을 정렬하여 앞에서부터 차례로 비교해준다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #include #define f(i,l,r) for(int i=l;i>a>>b; f(i,0,a)cin>>A[i]; f(i,0,b)cin>>B[i]; sort(A,A+a); sort(B,B+b); int i=0,j=0,ans=0; while(i
[ BOJ 백준 3482번 - Labyrinth ] 해설 및 코드 https://www.acmicpc.net/problem/3482 목적 임의의 free block 2개를 연결했을 때, 그 길이의 최대값을 구하자. 접근법 1. 백준 1967번 - 트리의 지름 문제와 같은 문제라고 보면 된다. 2. 인접한 free block으로 이동할 수 있고, 임의의 free block 2개 사이에는 길이 1개만 있다는 문제의 조건에 따라, Labyrinth는 트리구조를 갖는다. 3. 모든 period를 이어서 이를 트리의 형태로 보면, 어느 지점을 트리의 노드로 보아야 하는지 명확해질 것이고, 위 문제와 동일하다는 것을 알 수 있을 것이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30..
[ BOJ 백준 2533번 - 사회망 서비스(SNS) ] 해설 및 코드 https://www.acmicpc.net/problem/2533 목적인접한 두 개의 정점중 하나는 무조건 얼리 어답터여야 하며, 이 조건 하에 얼리 어답터의 최소 인원수를 구하자. 접근법1. 동적 계획법으로 접근하자. 인접한 정점은 조건에 따라 얼리 어답터로 선정하여 최소 값을 도출해 낸다. 12345678910111213141516171819202122232425262728293031323334353637#include#define f(i,l,r) for(int i=l;i>n; f(i,1,n){ int u,v;cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } memset(s, -1, sizeof(s)); cout
[ BOJ 백준 1949번 - 우수 마을 ] 해설 및 코드 https://www.acmicpc.net/problem/1949 목적 우수 마을 선정 기준('우수 마을'은 서로 인접할 수 없고, '우수 마을'이 아닌 마을은 '우수 마을'과 인접해야 한다.)에 따라, N개의마을중 몇개의 마을을 우수마을로 선정하여 인원의 합이 최대가 되게 만들자. 접근법 1. 트리의 성질에 따라 사이클에 관한 고민을 하지않아도 된다. 2. 우수 마을이 아닌 마을이 몇개 까지 인접가능한지 따위의 것을 고려하지 않아도 된다. 그냥 인접해도 무방하다는 가정으로 설계해도 최대값을 구하는 과정에서 걸러진다. 3. 우수마을과 인접한 마을만 우수마을에서 제외시키는 조건만 가지고, 간단히 DP로 해결하자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ..

티스토리툴바