2017/05 썸네일형 리스트형 BOJ)5670 휴대폰 자판 문제:icpc.me/5670 입력으로 들어오는 모든 문자열을 trie에 저장한 후 현재 확인중인 문자에서 다음 문자로 넘어가는 경로가 2 이상인 경우나 해당 지점에서 문자열이 끝나는 경우가 버튼을 눌러야 하는 경우이니 카운트를 증가시켜주어 return하는 쿼리를 구현하여 해결 가능하다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include #include #include #include #include using namespace std;struct trie { trie *go[26]; int gocnt; bool finished; trie() { go.. 더보기 제1종 스털링 수 원소의 개수가 N인 집합을 구분되지 않는 K개의 원순열로 분할하는 방법의 수이다. 이를 D[N][K]로 정의하면 D[N][K]=D[N-1][K-1]+(N-1)*D[N-1][K] 라는 점화식을 얻을 수 있다. 관련 문제: https://www.acmicpc.net/problem/1413 더보기 Minimum Path cover in DAG DAG(Directed Acyclic Graph)에서 모든 정점을 커버하는 겹치지 않는 최소의 경로의 수를 구하는 문제 전체 정점의 수가 V 커버한 경로상의 간선이 X라면 V-X개의 경로로 커버할 수 있다. 따라서 X를 최대화 시켜야한다. 간선을 고를 때 제약 조건은 한 정점이 선택 될 때 오직 하나의 indegree와 오직 하나의 outdegree가 선택되어야 한다는 점이다. 즉, indegree와 outdegree가 최대한으로 매칭되어야 한다. 이를 이용하여 indegree를 상징하는 정점과 outdegree의 정점을 상징하는 정점으로 그래프를 구성하여 해당 그래프의 이분 매칭을 구함으로서 Minimum Path cover in DAG를 구할 수 있다. 참조: http://koosaga.com/ent.. 더보기 BOJ)5624 좋은 수 문제:icpc.me/5624 좋은 수의 조건은 나보다 먼저 들어온 수 i, j ,k 의 합이 나와 같은 경우가 존재하는 경우이다. 우리는 이 수식을 i+j+k=x 로 생각할 수 있고 이 수식을 i+j=x-k로 바꿔 생각할 수 있다. 그러면 우리는 x를 받기전에 들어온 모든 수들의 합의 셋(i+j)들을 배열로 저장하여 O(1)만에 존재하는지 확인할 수 있다. 고로 모든 x-k에 대하여 같은 i+j가 존재하는지 확인해 준다면 O(N^2)에 문제를 해결할 수 있다. 1234567891011121314151617181920212223#include #include #define mid 200000using namespace std;int a[5010], n, b[400040], res;int main() { s.. 더보기 BOJ)12961 체스판2 문제:icpc.me/12961 체스판에 조건을 만족시키면서 동시에 채울 수 있는 타일의 최대 개수를 출력하는 문제이다. 타일의 모서리가 항상 검은칸을 덮게 체스판에 채울 경우 인접한 두 칸은 한 칸은 홀수 행에 한 칸은 짝수 행에 위치함을 알 수 있다. 고로 우리는 하얀 칸중 홀수 -> 검은 칸 -> 하얀 칸중 짝수 로 플로우를 흘려주어 얻을 수 있는 최대 유량이 답이 됨을 알 수 있다. 단 이 때 검은 칸을 통하여 플로우는 1만 흘러야 하므로 검은 칸을 정점 분할 시켜주어 정점 사이의 capacity를 1로 주어 풀어야한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545.. 더보기 BOJ)3654 L퍼즐 문제:icpc.me/3654 L퍼즐 모양으로 패턴을 완성시킨다고 가정하였을 경우 B 정점은 인접한 W정점중 하나는 홀수행의 정점에 하나는 짝수행의 정점에 매칭이 되어야 한다. 따라서 두개의 플로우 모델링을 하여 하나는 홀수행의 W들과 B의 최대 매칭 하나는 짝수행의 W들과 B의 최대 매칭을 구한 뒤 두 값과 B의 개수가 같은지와 모든 W의 수와 2*B가 같은지 두 경우를 검사해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394.. 더보기 BOJ)13308 주유소 문제: icpc.me/13308 1->n까지의 최소 비용을 원하는 문제이므로 다익스트라로 해결해줄 수 있다. 다만 문제에서 비용과 거리가 동시에 존재하므로 현재 보는 경로상에서 정점 x까지 순회하는 동안 발견한 가장 저렴한 주유소의 주유가격을 저장하여 d[here][mincost]로 2차원 테이블을 잡아 문제를 해결해주어야 한다. 1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #include #include #include using namespace std;typedef long long ll;vector vt;ll n, m, l[2550], x, y, z, d[2550][2550], r.. 더보기 이전 1 다음