2017/06/27 썸네일형 리스트형 UVaOJ)12797 Letters 문제:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4662 NxN의 맵이 주어질 때 1,1에서 n,n까지의 최단거리를 구하는 문제이다. 단 제약조건이 있는데 발판으로 주어지는 알파벳중에 대문자나 소문자 하나를 정해놓고 일관성있게 밟아야 한다. 알파벳이 최대 10개밖에 없기 때문에 상태에 대하여 비트마스킹을하여 넘겨주어 BFS를 1024번만 돌려주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include #incl.. 더보기 UVaOJ)11765 Component Placement 문제: https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2865 N개의 정점이 있을 때 N개의 정점이 상단에 연결되어야 하는지 하단에 연결되어야 하는지 여부를 구해주어야 하는 문제이다. 각각 상단에 연결되었을 때와 하단에 연결되었을 때의 비용이 주어지며 반드시 상단에 연결되어야 하는 경우, 반드시 하단에 연결되어야 하는 경우, 둘다 가능한 경우가 주어진다. 이 후 M개의 정보가 주어지는데 이 정보는 x 와 y 정점이 같은 곳(상단or 하단)에 연결되지 않았을 경우 생기는 추가비용이다. 이 때 모든 정점을 연결하였을 때 최소비용을 구하는 문제이다. 이 문제를 최소컷 문제로 변형해서 푼다고 생각을 하면 하나의.. 더보기 UVaOJ)12159 Gun Fight 문제:https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=3311 N개의 power가 존재하는 점이 주어지고 진영을 가르는 직선을 결정하는 두 점이 주어진다. 두 점으로 부터 진영을 갈라서 수가 적은 진영이 수가 많은 진영을 이기도록 최대한 매칭할 수 있는 수를 출력하는 문제이다. ccw를 이요하여 모든 점의 진영을 구해준 뒤 진영이 적은 쪽에서 진영이 많은 쪽으로 두 점 사이의 거리가 R이하이고 Power가 0이상이고 진영이 적은 쪽의 power가 진영이 많은쪽의 power보다 많은 두 점을 서로 매칭시켜준 뒤 최대매칭을 구해주면 된다. 123456789101112131415161718192021222324.. 더보기 이전 1 다음