본문 바로가기

알고리즘 관련/BOJ

BOJ)13166 범죄 파티 문제: icpc.me/13166 범죄자 N명과 친구 2*N명의 친구 관계와 임계점이 주어질 때 모든 범죄자가 친구랑 매칭 될 수 있는 파티 비용의 최솟값을 구하는 문제이다. 파티 비용의 최솟값을 파라메트릭 서치로 탐색할건데 이 때 탐색 기준은 mid를 파티 비용으로 정했을 때 모든 범죄자가 친구들과 매칭 되야 하므로 범죄자와 친구의 이분 매칭이 N이 됨을 기준으로 한다. 단, 정점의 개수가 20만이나 되므로 일반 이분매칭 소스로는 TLE를 보게되니 호프크로프트 카프 알고리즘을 이용하여 구해줘야 한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162.. 더보기
BOJ)3736 System Engineer 문제: icpc.me/3736 작업 세트와 서버로 이루어진 이분 그래프에서 최대 매칭을 구하는 문제이다. 정점의 개수가 10000개 이므로 일반 이분 매칭 소스로는 TLE가 나므로 hopcroft-karp 알고리즘을 이용하여 최대매칭을 구해줘야 한다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182#include #include #include #include #define INF 987654321using namespace std;struct hopcroft_karp { in.. 더보기
BOJ)2660 회장뽑기 문제:icpc.me/2660 두 사람의 친구 관계가 주어질 때 어떤 사람이 가장 먼 친구 관계가 n다리 걸쳐서 친구관계가 된다면 그 사람의 점수는 n점이라 할 때 최소 점수를 갖는 사람들이 회장 후보가 된다. 회장 후보를 출력하는 문제이다. 두사람의 친구 관계를 cost가 1인 간선으로 표현한다면 플로이드 워셜을 통하여 n:n 최단거리를 구해주면 두 사람의 친구 관계가 몇다리 걸쳐있는지 알 수있다. 이를 이용하여 답을 구해주면 된다. 123456789101112131415161718192021222324252627282930313233343536#include #include #include using namespace std;int n, x, y, a[51][51], r, b[51];int main().. 더보기
BOJ)1755 숫자놀이 문제: icpc.me/1755 m과 n 이 주어질 때 m부터 n까지의 사이의 수들을 숫자 하나당 영어로 표현하였을 때 정렬된 순서대로 숫자를 출력하면 된다. map을 이용하여 string 정렬해주면 해결해줄 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142#include #include #include #include #include using namespace std;map res;map cvt;int m, n, c;int main() { scanf("%d%d", &m, &n); cvt[0] = "zero "; cvt[1] = "one "; cvt[2] = "two "; cvt[3] = "three "; c.. 더보기
BOJ)1747 소수&팰린드롬 문제:icpc.me/1747 N보다 큰 수 중에서 소수이면서 팰린드롬인 가장 작은 수를 구하는 문제이다. 에라토스테네스의 체를 이용하여 소수들을 구해놓은 뒤 N보다 큰 수 중에서 팰린드롬인지 검사해주면 된다. 123456789101112131415161718192021222324252627282930313233343536#include #include using namespace std;bool p[2000001];int n;bool ck(int *a, int lo, int hi) { if (lo >= hi)return 1; if (a[lo] != a[hi])return 0; return ck(a, lo + 1, hi - 1);}bool chk(int x) { int c = -1; int a[8]; wh.. 더보기
BOJ)10835 카드게임 문제: icpc.me/10835 오른쪽 카드를 버릴 때 점수를 얻을 수 있을 때 얻을 수 있는 최고 점수를 구하는 문제이다, dp[x][y] b[y]) dp[x][y]=max(dp[x][y],dp[x][y+1]+b[y]) 라는 점화식을 통하여 문제를 해결할 수 있다. 12345678910111213141516171819202122232425#include #include #include #define INF 987654321using namespace std;int dp[2001][2001], n, a[2001], b[2001];int func(int x, int y) { if (x == n || y == n)return 0; int &ret = dp[x][y]; if (ret != -1)return r.. 더보기
BOJ)7535 A Bug's Life 문제: icpc.me/7535 서로 성별이 다른 두 벌레들의 정보가 주어질 때 vaild한지 여부를 묻는 문제이다. 우리는 두 벌레들의 정보가 들어온다는 걸 이용하여 2-SAT 모델링을 통하여 문제를 해결 할 수 있다. A와 B가 들어 왔을 때 두 벌레의 성별이 다르다는 걸 (A||B)&&(!A||!B)로 표현해준 뒤 이를 이용하여 2-SAT 모델링을 한 뒤 vaild 여부를 판단해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include #include #include #include #include .. 더보기
BOJ)3747 완벽한 선거! 문제: icpc.me/3747 문제에서 A||B의 셋이 M개가 주어지고 M개의 모든 셋이 동시에 참이 될 수 있는 지 여부를 묻는 문제이므로 2-SAT 모델링을 통해 문제를 해결할 수 있다. 주어진 조건대로 간선을 연결해준 뒤 2-SAT 모델링을 통하여 참 여부를 판단하여 출력해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include #include #include #include #include using namespace std;struct TwoSAT { int n, c, sccc; vec.. 더보기
BOJ)8992 집기 게임 문제: icpc.me/8992 두 선분을 최대한 집으면서 점수를 최대한 많이 얻으려고 할 때 집을 수 있는 선분의 개수와 최대 점수를 구하는 문제이다. 우리는 두선분을 집는걸 우선시 해야하므로 두선분을 동시에 집는걸 capacity를 이용하여 모델링해주며 이 때 두선분을 집을 때 얻는 점수를 cost로 모델링해준 뒤 MCMF를 통하여 답을 구해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102.. 더보기
BOJ)10937 두부 모판 자르기 문제: icpc.me/10937 두부를 1x2 혹은 2x1 모양으로 자르는데 자르는 두부에 써있는 알파벳에 따라 점수를 다르게 받는다고 한다. 이 때 최대 점수를 받도록 두부를 자르는 경우를 출력하는 문제이다. 우리는 두부판을 검은색과 흰색으로 이루어진 체스판으로 생각하면 항상 두부는 검은색 1개 흰색 1개로 매칭된다는걸 알 수 있다. 따라서 우리는 결국 이분 그래프에서의 최대 매칭을 구하면서 그 때의 최대비용을 구해야하는데 매칭이 안되는 경우도 있으니 이분 그래프중 소스에 매칭 되는 부분들을 전부 싱크로 1씩 capacity를 준다. 이후 모든 간선의 capacity를 1로 주고 점수에 맞게 cost를 준뒤 MCMF를 이용하여 maximum cost를 구해내면 된다. 1234567891011121314.. 더보기

티스토리툴바