Problem Solving102 SRM 707 Div.1 Kriii형이 또 다시 스름 윈을 했다ㅋㅋ 나는 오랜만에 해보았는데 0점 받지 않아서 다행이라 생각한다. 몇 가지 고려 안해서 미디움을 놓친 건 정말 아쉽다.250pts(Passed System Test) ㄹ자로 만드는 전략을 통해 맵을 만들어나가면 된다. 단, ㄹ자로 만드는 과정에서 경로가 2씩 증가됨에 주의한다.class MazeConstruct { public: vector solve(vector ans, int k) { int s = ans.size(); for (int i = 1; i 2017. 1. 31. 문제풀기 - SDS_PRO_8_3 문제 링크(koitp.org/problem/SDS_PRO_8_3/)동적계획법으로 해결할 수 있다.D(i, j) : i번째 문제까지 해결했을 때에, 다음 달에 주어야하는 돈이 j일 때에 필요한 최소 # of monthsi번째 문제를 해결할 때에 같이 해결하는 문제 번호 중 가장 앞 번호를 k로 놓고, 점화식을 유도할 수 있다. 2017. 1. 29. BOJ 1995 폐쇄회로 문제 링크(icpc.me/1995)CCW로 각 CCTV에서 보이는 선분들의 영역을 구할 수 있다. 원형으로 구성된 영역을 선으로 펴서 동적계획법으로 풀면 된다.dp(seg(i).s) = min(dp(j))+seg(i).w (seg(i).s≤j≤seg(i).e+1)이런 점화식이 나오고, 이 부분을 BIT로 구현하면 에 풀 수 있다. 2017. 1. 25. 술 약속 - 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. 이전 1 ··· 3 4 5 6 7 8 9 ··· 21 다음
