본문 바로가기

2017/03

BOJ)14428 수열과 쿼리 16 문제: icpc.me/14428 i j 가 주어질 때 Ai ~ Aj 까지의 최솟값의 인덱스를 출력하는 문제이다. 세그먼트 트리를 이용하여 구간의 가장 작은 위치의 인덱스를 저장해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include #include #define INF 987654321using namespace std;int n, m, seg[400000], x, y, z, a[100001];int uquery(int pos, int node, int x, int y) { if (pos 1; int q1 = uquery(pos, node * 2, x, mid); int q.. 더보기
BOJ)3640 제독 문제: icpc.me/3640 경로가 겹치지 않게 두가지 방법으로 목적지 까지 갈 때 사용되는 최소 비용을 구하는 문제이다. 경로가 겹치지 않는 두가지 방법을 구하는 모델링은 네트워크 플로우 이론에서 정점 분할을 한 뒤 간선과 정점 사이의 모든 capacity를 1으로 준 뒤 플로우를 흘려주는 것으로 가능하다. 이 때 두가지 방법으로 이동할 때 드는 최소 비용을 구하는 문제이므로 MCMF를 이용하여 minimum cost를 구하되 sink까지 플로우를 두번만 흘려주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697.. 더보기
BOJ)11409 열혈강호 6 문제: icpc.me/11409 Maximum Cost Maximum Flow를 구하는 문제이다. 기존 MCMF 모델링에서 cost만 음수값으로 취해준 뒤 계산해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788#include #include #include #include #define INF 987654321using namespace std;struct Edge { int v, cost, cap, rev; Edge(int v, int cost.. 더보기
BOJ)11408 열혈강호5 문제: icpc.me/11408 직원들이 일을 할 수 있을 만큼 최대한 시킬 때 지급해야 하는 월급의 최솟값을 같이 구해주는 문제이다. 문제에서 요구하는 조건은 MCMF로 구해줄 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788#include #include #include #include #define INF 987654321using namespace std;struct Edge { int v, cost, cap, rev; Edge(int v,.. 더보기
BOJ)9370 미확인 도착지 문제:icpc.me/9370 시작지점이 주어지고 이들의 도착 예정 경로들이 주어진다. 이 때 주어진 도착 예정 경로로는 무조건 최단경로로 이동할 때 어떤 한 간선을 통과하는지 여부를 묻는 문제이다. 우리는 시작지점에서 다익스트라를 실행하여 모든 정점으로의 최단거리를 전부 계산해준 뒤 주어진 간선에서 부터 다시 다익스트라를 실행하여 주어진 간선에서 부터의 최단 거리를 구해준다. 그리고 나서 도착 예정경로중 (시작정점에서 도착 예상 정점의 최단거리 = 시작정점에서 주어진 간선까지의 최단거리 + 주어진간선부터 도착 예상정점으로의 최단거리) 인 정점들을 출력해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344.. 더보기
BOJ)1252 이진수 덧셈 문제: icpc.me/1252 두 이진수를 입력받아 더한 결과를 출력하는 문제이다. string 변수 a,b를 선언하여 크기에 따라서 순서를 강제시켜준 뒤 덧셈 연산을 해주면 된다. 이 때 캐리 변수를 생성하여 관리해주면 덧셈 계산에 용이하다 주의 할 점은 0으로 시작하는 문자열이 들어올수도 있다.(이걸 안읽어서 3번이나 틀렸다.) 문제를 자세히 읽어야한다는 교훈을 얻은 문제이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include #include #include #include using namespace std;string x, y;int a[100], of, f;int .. 더보기
BOJ)2636 치즈 문제: icpc.me/2636 공기와 닿는 부분의 치즈가 하루마다 녹을 때 치즈가 다 녹는데 걸리는 시간과 전부 다 녹기 직전 치즈의 개수를 출력하는 문제이다. bfs를 이용하여 공기와 닿는 부분을 기록해준 뒤 날이 바뀔 때 치즈를 갱신해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#include #include #include #include using namespace std;int n, m, a[101][101], b[101][101], r, f;int dx[] = { 0.. 더보기
BOJ)1629 곱셈 문제:icpc.me/1629 A^B(MOD C)를 구하는 문제이다. A,B,C가 2^31까지 들어오므로 단순 구현으로는 오버플로우나 시간초과를 받게 될 것이다. 하지만 우리는 분할정복을 이용하여 logB 시간에 A^B를 구해줄 수 있다. 1234567891011121314151617181920212223#include #include using namespace std;typedef long long ll;ll a, b, c;ll power(ll x, ll y) { ll ret = 1; while (y > 0) { if (y % 2) { ret *= x; ret %= c; } x *= x; x %= c; y /= 2; } return ret;}int main() { scanf("%lld%lld%lld",.. 더보기
BOJ)1201 NMK 문제: icpc.me/1201 N M K 가 주어질 때 1~N까지의 수로 이루어진 수열에서 최대 부분 증가 수열의 길이가 M이고 최대 부분 감소 수열의 길이가 M인 수열을 출력하는 문제이다. 우리는 부분 감소 수열의 개수 K개의 세그먼트를 만들면서 하나의 세그먼트는 전부 증가하는 수로 이루어져 있으며 그 세그먼트의 최대 길이는 M이 되도록 만들어주면 된다. M+K-1 더보기
BOJ)12026 BOJ 거리 문제:icpc.me/12026 B->O->J->B 로 이동가능한 경로를 n^2 으로 전부 간선을 연결해 준 뒤 다익스트라 알고리즘을 이용하여 최단거리를 구해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940#include #include #include #include #include #include #include using namespace std;int n, dp[1001];string a;vector vt;int main() { memset(dp, -1, sizeof(dp)); scanf("%d", &n); vt.resize(n + 1); cin >> a; for (int i = 0; i 더보기

티스토리툴바