본문 바로가기

알고리즘 관련/BOJ

BOJ)11410 칙칙폭폭 문제: icpc.me/11410 기차가 1->N까지 이동할 때 도시 i에서 j로 이동하는 사람의 수와 그때 기차요금이 주어질 때 기차에 동시에 최대 p명의 사람이 탈 수 있을 때 기차가 낼 수 있는 최대 수익을 출력하는 문제이다. i->i+1(i = 1~N)에 대하여 capcity를 INF, cost를 0으로 간선을 생성해주고 i 에서 j로 이동하는 경우에 이동하는 사람의 수를 capacity로 기차요금을 cost로 간선을 생성해 준 뒤 소스에서 ->1로 N에서 -> 싱크로 capacity p의 간선을 연결해 준 뒤 MCMF를 통하여 maximum cost를 구해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041.. 더보기
BOJ)9413 제주도 관광 문제: icpc.me/9413 시작 지점과 도착 지점 그리고 중간 경로상의 모든 정점들이 겹치지 않게 두 경로를 만들 때 가장 많은 정점을 순회하는 경우의 순회한 정점 수를 출력하는 문제이다. 우리는 정점을 분할 시킨 뒤 정점 사이의 capacity를 1로 주어서 정점이 중복 선택 안되게 가능하고 가장 많은 정점은 maximum cost를 구하면 되므로 MCMF를 이용하여 해결해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939.. 더보기
BOJ)2311 왕복 여행 문제:icpc.me/2311 N개의 나라들이 있을 때 1~N까지 도시를 왕복할 때의 최소비용을 구하는 문제이다. 단 이 때 한번 갔던 경로로는 다시 이동할 수 없다. 우리는 소스->1->N->싱크로 그래프를 모델링 해준 뒤 소스->1 N->싱크의 간선만 capacity를 2로 주고 나머지 간선의 capacity를 1로 준 뒤 MCMF를 이용하여 mincost를 구할 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081#include #include #include #inclu.. 더보기
BOJ)8892 팰린드롬 문제: icpc.me/8892 k개의 단어가 주어질 때 두 단어를 조합하여 팰린드롬이 되는 경우 출력하는 문제이다. string 배열에 모든 단어들을 받아준 뒤 검사해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637#include #include #include #include using namespace std;int t, k, f;string a[101];bool isPal(string x) { for (int i = 0; i a[i]; for (int i = 0; i 더보기
BOJ)13576 Prefix와 Suffix 문제: icpc.me/13576 prefix와 suffix가 같은 모든 부분문자열은 pi배열을 이용하여 전부 구해줄 수 있다. length -> pi[length] -> pi[[pi[length]]] ... 이런식으로 하지만 이때 부분 문자열의 등장횟수도 구해줘야 한다. suffix의 부분 문자열 등장횟수는 LCP를 이용하여 O(N)에 처리해줄 수 있다. 현재 확인중인 i번째 suffix의 등장횟수는 LCP[i+1]~ LCP[max] 중에서 연속으로 부분 문자열 i의 길이보다 큰 LCP의 개수로 처리해줄 수 있다. 아래 코드에서 dp배열에 suffix의 등장횟수가 담긴다. 12345678910111213141516171819202122232425262728293031323334353637383940414.. 더보기
BOJ)13506 카멜레온 부분 문자열 문제: icpc.me/13506 접두사와 접미사가 동시에 될 수 있는 최대 부분 문자열 중 접두사와 접미사가 둘다 아니게도 등장하는 부분 문자열을 카멜레온 부분 문자열이라고 할 때 카멜레온 부분 문자열중에서 가장 길이가 긴 부분 문자열을 출력하는 문제이다. KMP의 pi배열을 이용한다면 우리는 prefix와 suffix를 동시에 만족시키는 모든 문자열의 길이를 알 수 있다 // pi[l] -> pi[pi[l]] ->pi[pi[pi[l]]] ... 이 때 prefix와 suffix를 둘 다 만족안하게 등장하는 경우는 pi[0]과 pi[length]를 제외하고 현재 확인하는 부분문자열의 길이와 같은 pi[x]가 존재하는 경우이다. 1234567891011121314151617181920212223242526.. 더보기
BOJ)1585 경찰 문제: icpc.me/1585 들어가는 시간과 나오는 시간들의 셋을 이분 매칭시켜 mincost와 maxcost를 구하는 문제이다. 소스-> 들어가는 시간 -> 나오는 시간 ->싱크로 모델링을 해준 뒤 MCMF를 이용하여 mincost와 maxcost를 구하면 된다. 이 때 비용은 들어가는 시간->나오는 시간 일 때 min((S-T)*(S-T),F)으로 정의된다. 주의 할점은 maximum flow가 n이 안될 때 -1을 출력하는데 한번만 출력해야한다. 필자의 경우 두번 출력하여 3번 틀렸다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364.. 더보기
BOJ)4716 풍선 문제: icpc.me/4716 모든 팀에게 풍선을 달아줄 때 풍선을 달기 위해 이동해야하는 최소 거리를 출력하는 문제이다. 그래프 모델링을 소스->방A,B -> N개의 팀-> 싱크 로 준 뒤 거리를 cost로 풍선을 capacity로 한 MCMF의 minimum cost를 출력하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889#include #include #include #include #define INF 987654321using name.. 더보기
BOJ)11407 책 구매하기3 문제: icpc.me/11407 N명의 사람과 M개의 서점이 있을 때 각 사람들이 살 수 있는 책의 수와 각 서점이 파는 책의 개수 그리고 i번째 사람이 j번째 책을 살때의 비용과 살 수 있는 개수가 주어질 때 최대로 책을 사면서 비용을 최소로하는 경우의 살 수 있는 책의 개수와 비용을 출력하는 문제이다. 우리는 살 수 있는 책의 개수를 capacity로 비용을 cost로 그래프를 모델링 해준 뒤 MCMF를 실행시켜주면 원하는 답을 구할 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677.. 더보기
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.. 더보기

티스토리툴바