2017/03 썸네일형 리스트형 BOJ)10937 두부 모판 자르기 문제: icpc.me/10937 두부를 1x2 혹은 2x1 모양으로 자르는데 자르는 두부에 써있는 알파벳에 따라 점수를 다르게 받는다고 한다. 이 때 최대 점수를 받도록 두부를 자르는 경우를 출력하는 문제이다. 우리는 두부판을 검은색과 흰색으로 이루어진 체스판으로 생각하면 항상 두부는 검은색 1개 흰색 1개로 매칭된다는걸 알 수 있다. 따라서 우리는 결국 이분 그래프에서의 최대 매칭을 구하면서 그 때의 최대비용을 구해야하는데 매칭이 안되는 경우도 있으니 이분 그래프중 소스에 매칭 되는 부분들을 전부 싱크로 1씩 capacity를 준다. 이후 모든 간선의 capacity를 1로 주고 점수에 맞게 cost를 준뒤 MCMF를 이용하여 maximum cost를 구해내면 된다. 1234567891011121314.. 더보기 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.. 더보기 이전 1 2 3 4 5 다음