전체 글110 술 약속 - 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. 로다 - 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. 이전 1 ··· 4 5 6 7 8 9 10 ··· 22 다음
