Script / CSS

G1sUtil.js

G1sBlogger.js

G1sNavigationList.js

G1sCode

Posts List


2014년 4월 13일 일요일

[Algospot] 남극기지

남극기지

문제 ID : ARCTIC
시간제한 : 1000ms
메모리 제한 : 65536kb
제출횟수 : 1702
정답횟수 (비율) : 404(23%)
출제자 : JongMan
출처 : 연습문제

최소비용신장 트리에 대한 문제이네요.
프림알고리즘을 응용하여 해결하였습니다.

총 10번만에 성공했네요.
머릿속으로 그린걸 바로 소스로 적용하다보니 어디가 틀렸는지 파악하기가 힘들군요.
결국 초기 설계부터 문제가 있어 다시 설계하였습니다.

프림알고리즘을 그대로 이용하였더라면 설계가 틀리지는 않았겠지만...
응용을 하여 좀 더 효율적으로 답을 구할 수 있는 방법을 찾다보니 설계에서 실수가 있었네요.
결국 결과는 최소비용신장트리는 아니게 되었군요.
하지만 이 문제의 답을 구하는데는 부합하고, 시간을 단축할 수 있었습니다.

198487ARCTICGOnecpp771B정답6ms10

결과는 만족스럽네요.
시간을 좀 더 단축할 수도 있을 것 같긴한데 소스만 길어지고 결과는 그대로 일 수도 있어 우선 이정도로 하겠습니다.

>>소스보기

댓글 없음:

댓글 쓰기