2017/03 썸네일형 리스트형 BOJ)1326 폴짝폴짝 문제: icpc.me/1326 각 징검다리에 숫자가 써있고 해당 징검다리에서는 숫자의 배수만큼 떨어져 있는 징검다리까지 점프 할 수 있을때 a에서 b까지 의 최단거리를 출력하는 문제이다. 해당 징검다리에서 갈 수 있는 모든 징검다리까지 cost가 1인 간선을 연결해주고 다익스트라를 이용하여 최단거리를 구해줄 수 있다. 이 때 주의할 점은 배수 이기 때문에 나보다 작은 지점으로도 점프할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637#include #include #include #include #include using namespace std;int n, a[10001], s, e, dp[10001];vector vt;in.. 더보기 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.. 더보기 이전 1 2 3 4 5 다음