전체 글 (33) 썸네일형 리스트형 [ICPC 본선 대비 뇌셋] Day 21 ICPC 본선 대비 뇌셋 포스팅 대망의 마지막 날이다. 작년에 못풀었던 문제들중 한문제인 2019년 ICPC Korea regional E번을 생각해봤다. 자료구조까지는 생각하지 않았지만, $O(N^2 lg(N))$에 풀리게 생겼다. 백준 17972번 Network Vulnerability www.acmicpc.net/problem/17972 17972번: Network Vulnerability Your program is to read from standard input. The first line contains a positive integer n representing the number of intervals, where n ≤ 2,000. In the following n lines, each.. [ICPC 본선 대비 뇌셋] Day 20 이제 이 제목의 글도 내일이면 끝이다.백준 10167번 금광 www.acmicpc.net/problem/1016710167번: 금광첫 줄에는 금광들의 개수 N (1 ≤ N ≤ 3,000)이 주어진다. 이어지는 N개의 줄 각각에는 금광의 좌표 (x,y)를 나타내는 음이 아닌 두 정수 x와 y(0 ≤ x,y ≤ 109), 그리고 금광을 개발하면 얻게 되는 이익 www.acmicpc.net오늘은 좀 쉬어가는 느낌으로 금광을 짰다. 풀이는 대충 창기한테 들었고, 구현을 해봤는데 시간이 좀 느리게 나왔다. 다른 여러 블로그에 풀이가 많으니 그걸 보는게 좋을 것 같다. 물론 이런 문제가 나오면 이메이미가 밀겠지만 어떻게 생겨먹은 세그인지는 알고싶어서.. 오늘 좀 놀았는데 그러기엔 죄책감이 들어서 재작년에서 어려웠던.. [ICPC 본선 대비 뇌셋] Day 19 백준 2427번 2012 지구 멸망 www.acmicpc.net/problem/2427 2427번: 2012 지구 멸망 3명씩 3개의 그룹으로 나누면, 각 그룹은 회의가 4분씩 걸리고, 다시 마지막에 3명이 회의에 참석해서 회의를 하면 4분이 걸리므로, 8분이 걸린다. www.acmicpc.net V가 i번, P가 j번 사용 될 때 가능한 최대 횟수가 얼마일지를 구해준 다음 이를 이용해서 최소 시간을 구해주면 된다. dp식은 다음과 같다. $dp[i][j] = max(dp[i][j], dp[i-1][k]*(j-k))$ for{k=j-2 ; k>= max(j-2050, 0) ; k--} dp가 왜 성립하는지에 대한 정당화가 필요하지만 개인적으로 다이아3 정도는 아닌 듯 하다. [증명] bottom top으.. 이전 1 2 3 4 5 6 7 ··· 11 다음
