본문 바로가기

알고리즘 관련/BOJ

BOJ)4627 뛰어라 도마뱀 문제: icpc.me/4627 도마뱀이 맨해튼 거리가 D이하인 거리를 이동 할 수 있을 때 탈출을 하지 못하는 도마뱀의 수를 정하면 된다. 문제를 잘 읽어보면 같은 시간에는 최대 하나의 도마뱀만 기둥에 서 있을 수 있고 기둥에는 최대 도약 횟수가 정해져 있다. 이를 이용하여 그래프를 모델링을 하면 소스->도마뱀들의 처음 위치 각 방-> 맨하탄 거리가 D이내인 방 외각->Destination 으로 모델링을 할 수 있다. 이 때 우리는 최대 도약 횟수를 생각해야 하므로 정점들을 분할하여 정점을 분할하는 간선의 가중치를 최대 도약횟수로 주고 최대유량을 구해주면 원하는 답을 얻을 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383.. 더보기
BOJ)13701 중복 제거 문제:icpc.me/13701 중복되서 입력 된 수를 제거하고 출력하면 되는 문제이다. 하지만 메모리 제한이 8MB밖에 안되기 때문에 수를 그냥 입력받아서 저장하기에는 무리가 있다. 그래서 비트마스킹을 이용하여 사용한 수에 해당하는 비트를 켜주고 수를 받았을 때 비트가 켜져 있는지 확인하고 출력하면 된다. 123456789101112131415161718#include #include using namespace std;int c[1 + (1 더보기
BOJ)1647 도시 분할 계획 문제: icpc.me/1647 최소 스패닝 트리를 구해주면 된다. 주의할 점은 하나인 마을을 두개로 나누고 싶다고 하고 있기 때문에 N-2개의 간선만 연결해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839#include #include #include using namespace std;vector vt;int n, m, a, b, c, r;int par[100010];int find(int x) { if (par[x] == x)return x; return par[x] = find(par[x]);}void merge(int x, int y,int z) { x = find(x); y = find(y); if (x ==.. 더보기
BOJ)4948 베르트랑 공준 문제: icpc.me/4948 n~2n 사이의 소수의 개수를 출력하면 되는 문제이다. 에라토스테네스의 체로 소수들을 구해 준 뒤 파셜섬의 차를 구해주면 된다. 12345678910111213141516171819202122232425#include #include using namespace std;bool p[270000];int s[270000];int n;int main() { p[0] = p[1] = true; for (int i = 2; i 더보기
BOJ)12842 튀김 소보루 문제: icpc.me/12842 m명의 사람이 튀김 소보루를 먹는 시간이 주어졌을 때 n번째 튀김 소보루를 누가 먹었는지 출력하는 문제이다. n과 m이 10만이고 개인이 소보루를 먹는 시간 t가 최대 1000이여서 시뮬레이션을 돌려도 시간내에 AC 받을 수 있었다. 123456789101112131415161718192021222324#include #include #include using namespace std;int n, s, m, x, r, t;int a[100010];int main() { scanf("%d%d%d", &n, &s, &m); for (int i = 1; i 더보기
BOJ)13505 두수 XOR 문제: icpc.me/13505 N개의 수 중에서 두 수를 정해 XOR한 값이 가장 크게 하는 문제이다. 두수가 XOR을 하여 가장 큰 수가 되려면 서로 다른 비트가 가장 많아야 할 것이다. 트라이를 이용하여 모든 수를 비트 순서대로 저장 한 후 이후 모든 수에 대해서 자기와 다른 비트를 따라가도록 하면 된다. 이때 가장 큰 수가 되야 하므로 비트는 높은 자리 수 부터 검사한다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485#include #include #incl.. 더보기
BOJ)12843 복수전공 문제: icpc.me/12843 n개의 강의가 주어질 때 서로 다른 학부의 강의면서 강의의 내용이 겹치는 강의는 두 강의중 하나만 수강할 때 최대로 수강할 강의 수를 구하는 문제이다. 내용이 겹치는 두 강의를 서로 연결해준다면 c학부와 s학부로 이루어진 이분 그래프가 나타나게 된다. 이때 이분 그래프에서 최대로 매칭되는 만큼 수업을 더 안들으면 되기 때문에 이분 매칭을 구해준 후 N에서 빼주면 답이 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include #include #include #include using namespace std;int n, m, x, y;char .. 더보기
BOJ)12841 정보대 등산 문제: icpc.me/12841 왼쪽 1번 지점에서 오른쪽 n번 지점까지 가는 최단 거리를 구하는데 이 때 횡단보도는 한번 밖에 못 건넌다는 전제가 있다. N개의 횡단보도를 건너는 케이스를 전부 확인을 해줘야 하는데 N이 10만이나 되기 때문에 모든 케이스를 직접 더해줄 경우 TLE를 받을 수 있다. 하지만 Partial sum을 이용한다면 왼쪽 오른쪽길의 횡단보도 기준으로 위 아래는 쉽게 구할 수 있다. 주의 할 점은 10만개의 횡단보도에 거리가 10만 까지 들어올 수 있으므로 long long을 사용해줘야 한다. 12345678910111213141516171819202122232425262728293031#include #include #define INF 999999999987654321using.. 더보기
BOJ)1865 웜홀 문제: icpc.me/1865 방향 그래프에서 시간이 거꾸로 간다는 개념이 나온다면 우선 벨만-포드를 생각해 볼 수 있다. 이때 주의 할 점은 도로는 방향이 없으므로 양 방향에 연결을 해줘야 한다. 문제에서 질문은 출발을 하였을 때 보다 시간이 되돌아 가 있는 경우가 있는지 확인하는 것인데 이것은 벨만-포드에서 음수 사이클 존재 여부를 확인하는 것과 동치다. 따라서 벨만-포드를 구현 한 뒤 음수 사이클 존재 여부에 따라 출력해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include #include #include #define INF 987654321using namespace std;in.. 더보기
BOJ)11999 Milk Pails 문제: icpc.me/11999 X,Y,M이 주어졌을 때 X와 Y를 이용하여 M을 넘치지 않도록 최대한 얼마나 채울 수 있는지 구하는 문제이다. X,Y,M이 전부 1000이하이기 때문에 이터레이터를 1000번씩 돌려주면 되는 쉬운 문제다.O(N^2) 1234567891011121314151617#include #include using namespace std;int x, y, m, r;int main() { freopen("input.txt", "r", stdin); scanf("%d%d%d", &x, &y, &m); for (int i = 0; i 더보기

티스토리툴바