Problem Solving102 포위 - SDS_PRO_9_5 문제 링크(koitp.org/problem/SDS_PRO_9_5/)A나라와 B나라의 병사들에 대해 각각 컨벡스헐을 구한다.그러면 A나라 컨벡스헐 내부에 있는 B나라의 병사 수와 B나라 컨벡스헐 내부에 있는 A나라의 병사 수를 구해야하는데, 편의상 전자에 대해서만 논하도록 하겠다.A나라 컨벡스헐의 윗부분과 아랫부분을 나누어 생각해보자.점 P가 A나라 컨벡스헐의 내부에 있다는 의미는 아래 1)과 2)를 모두 만족하는 것과 동치.1) P가 윗부분 컨벡스헐에 대해 오른쪽에 있다.2) P가 아랫부분 컨벡스헐에 대해 왼쪽에 있다.따라서 A나라 컨벡스헐의 점들과 B나라 병사들 전부를 X좌표 순으로 오름차순 정렬해서 two-pointer 기법으로 처리하면 선형에 모든 병사들에 대한 처리가 가능하다. 만약 B나라 병사의.. 2017. 1. 21. 248 게임 - USACO_2016OPENGOLD_248 문제 링크(koitp.org/problem/USACO_2016OPENGOLD_248/)dp(i, j) : i ~ j까지의 답dp(i, j) = max[(dp(i, k)==dp(k+1, j))x(dp(i, k)+1)] 2017. 1. 21. 합분해 - SDS_PRO_2_2 문제 링크(koitp.org/problem/SDS_PRO_2_2/)dp(i, j) : 합이 i일 때, 총 사용한 숫자의 개수가 j일 때의 경우의 수마지막 j번째 숫자로 k를 썼다고 하면, dp(i-k, j-1)의 값을 dp(i, j)에 누적해주면 된다. 2017. 1. 21. 고속도로 건설 - SDS_PRO_10_4 문제 링크(koitp.org/problem/SDS_PRO_10_4/)Kruskal Algorithm 2017. 1. 21. 워프 - SDS_PRO_10_3 문제 링크(koitp.org/problem/SDS_PRO_10_3/)dp(i) : i번 도시까지 도달하는 데에 필요한 최소 시간 2017. 1. 21. 이전 1 ··· 5 6 7 8 9 10 11 ··· 21 다음
