본문 바로가기

전체 글

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 더보기
BOJ)10775 공항 문제: icpc.me/10775 비행기가 도착하는 순서대로 게이트에 도킹을 하는데 한 게이트에는 오직 한대의 비행기만 도킹이 가능하다 이때 각각의 비행기는 1~g번째 게이트중 하나에 도킹할 수 있다는 정보가 들어올 때 최대로 도킹할 수 있는 비행기의 수를 출력하면 된다. g번째 게이트부터 도킹을 하는게 이득인 것임은 자명하므로 disjoint-set을 이용하여 g게이트에 도킹이 될 경우 다시 g게이트를 확인 할 때 g-1게이트를 확인 하도록 parent를 설정해주면 된다. 만약 find 호출에서 0을 호출하게 된다면 1~g번째 게이트는 모두 사용중인것이니 더 이상 도킹이 불가능 하므로 현재까지 도킹 된 횟수를 출력해 주면 된다. 12345678910111213141516171819202122#includ.. 더보기