전체 글 (33) 썸네일형 리스트형 [ICPC 본선 대비 뇌셋] Day 21 ICPC 본선 대비 뇌셋 포스팅 대망의 마지막 날이다. 작년에 못풀었던 문제들중 한문제인 2019년 ICPC Korea regional E번을 생각해봤다. 자료구조까지는 생각하지 않았지만, O(N2lg(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 다음 목록 더보기
