전체 글110 파티 참석하기 2 - PARTY2 문제 링크(koitp.org/problem/PARTY2/)STL 없이 코드를 작성해보았다. 우선, 이 문제에서 구하고자 하는 것은 max(dist(X→a)+dist(a→X))이다. dist(X→a)는 X번 학생의 기숙사 방에서 a번 학생의 기숙사 방에 이르는 최단거리이다. 따라서 이 문제는 주어진 그래프에 대해 dist(X→a)와 dist(a→X)를 계산하면 풀 수 있다. dist(X→a)는 주어진 그래프에서 점 X를 시작점으로 다른 점들에 이르는 최단 거리를 구하면 된다. dist(a→X)는 주어진 그래프의 간선 방향을 뒤집은 다음(간선의 시작점과 끝점을 바꿈), 위와 마찬가지로 계산하면 된다. 정리하면, 원래 주어진 그래프(G1)에 대해 점 X에서 단일 출발점 최단경로 알고리즘을 수행하고, 주어진 그.. 2017. 2. 7. 호감도 - GOOD_FEELING 문제 링크(koitp.org/problem/GOOD_FEELING)랜덤으로 선분을 결정한 다음, 답의 여부를 확인하는 걸 상수번 반복.20% 이상이어야 하기 때문에 답이 YES라면 높은 확률로 추출 가능.C++은 빨라서 100점이 나오는데, Python은 TLE 나온다ㅠㅠ 하지만 답은 다 맞음. 2017. 2. 5. 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. 이전 1 ··· 3 4 5 6 7 8 9 ··· 22 다음
