Problem Solving/KOITP21 문제풀기 - SDS_PRO_8_3 문제 링크(koitp.org/problem/SDS_PRO_8_3/)동적계획법으로 해결할 수 있다.D(i, j) : i번째 문제까지 해결했을 때에, 다음 달에 주어야하는 돈이 j일 때에 필요한 최소 # of monthsi번째 문제를 해결할 때에 같이 해결하는 문제 번호 중 가장 앞 번호를 k로 놓고, 점화식을 유도할 수 있다. 2017. 1. 29. 술 약속 - SDS_PRO_6_6 문제 링크(koitp.org/problem/SDS_PRO_6_6/)i번째 약속이 j번째 약속 앞에 위치할 때, 그 조건을 알아보자.A + S*D(i) + (S+T(i))*D(j) ≤ A + S*D(j) + (S+T(j))*D(i)T(i)D(j) ≤ T(j)D(i)i와 j 사이에 임의의 약속들이 있어도 도출되는 식은 변함없다.따라서 i≤j에 대해 T(i)D(j) ≤ T(j)D(i)가 되도록 정렬하고 순서대로 계산하면 된다. 2017. 1. 24. cow party - SDS_PRO_4_5 문제 링크(koitp.org/problem/SDS_PRO_4_5/)X에서 각 농장으로 가는 최단거리는 X에서 SPFA각 농장에서 X로 오는 최단거리는 주어진 그래프에서 방향을 뒤집은 후, X에서 SPFA 2017. 1. 24. 저주 인형 - COCI_2016C2_VUDU 문제 링크(koitp.org/problem/COCI_2016C2_VUDU/)Prefix sum과 index를 pair로 정한다.Prefix sum 오름차순으로 정렬하고, index에 대해 fenwick tree로 관리하면서 계산하면 된다.O(N log N) 2017. 1. 23. 오크 나무 - COI_2010_HRASTOVI 문제 링크(koitp.org/problem/COI_2010_HRASTOVI/)단순한 좌표압축 + 이분탐색. 직사각 영역의 꼭짓점을 2번 카운팅 하지 않는 것에 주의. 2017. 1. 23. 이전 1 2 3 4 5 다음
