본문 바로가기

Problem Solving/KOITP21

로다 - COCI_2016C2_SAVEZ 문제 링크(koitp.org/problem/COCI_2016C2_SAVEZ/)해싱을 이용한 동적계획법으로 해결할 수 있다. D(i, p, q) : i번째 문자열까지 고려했을 때, prefix 해시값이 p, suffix 해시값이 q일 때의 최대 텔레포트 횟수i번째 문자열의 prefix와 suffix들에 대해 D(i-1)의 값으로 D(i, p, q)값을 갱신하면 된다.그런데 여기서 첫번째 차원인 i는 (p, q)가 누적되는 성질에 따라 불필요하게 된다. 2017. 1. 22.
구간 나누기 - KOITP_201601_INTERVALDIVISION 문제 링크(koitp.org/problem/KOITP_201601_INTERVALDIVISION/)동적계획법으로 해결할 수 있다.dp(k, i) : i번째 수까지 k개의 구간을 정했을 때의 최적해dp(k, i) = max[dp(k-1, j) + max(A(j+1)~A(i)) - min(A(j+1)-A(i))]여기서 max( )와 min( )을 계산하는데 O(N)이 걸려서 한 가지 변형을 한다.dp_contain_max(k, i) = max[dp(k-1, j) + max(A(j+1)~A(i))]dp_contain_min(k, i) = max[dp(k-1, j) - min(A(j+1)~A(i))]그러면 dp(k, i) = max[dp_contain_max(k, i) - A(i), dp_contain_min(.. 2017. 1. 22.
포위 - 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.

티스토리툴바