Hanoi Tower
http://211.228.163.31/30stair/hanoi1/hanoi1.php?pname=hanoi1 문제를 요약하자면 현재상태의 하노이 탑이 주어졌을때 1,2,3번 기둥중 어떤기둥으로 옮기는지는 상관없고, 최소의 이동으로 모든 조각을 한곳에 모을때 최소이동과 어디로 모으는 것이 최적인지 구하는것이다. 일단 이문제는 linear 하게 풀릴수 있다. 가장 쉽게 떠올릴수 있는 방법이 모든 경우를 다해보는 backtracking 기법인데. 이문제의 실제 N범위가 100,000인걸 감안한다면 으론 해결할수 없다. 그렇다면 어떻게 접근해야 풀수 있을까? 1) 우선 우리는 N개의 하노이를 한 기둥에서 다른기둥으로 옮기기 위해 이동해야하는 최소횟수는 임이 자명하다. 2) 그리고 우리가 최종적으로 옮겨야할 목적..
I'm coder 2nd!!
오랜만에 글써보내요 다름이 아니라 최근에 참가한 모의고사에 대한 풀이를 올려볼까 합니다. 결과페이지 : http://www.koistudy.net/bbs/moi/2nd/result.php 저는 대회때 1,2번을 풀고 3,4번을 고민하다가 결국 몇점 받지도 못했네요 ㅋㅋ 1. Sum (http://koistudy.net/?mid=prob_page&NO=502) 일단 두가지 방법으로 접근이 가능한것 같습니다. 첫번째 방법) 우선 인 모든 a,b의 쌍을 찾아내는것이 문제입니다. 위 식을 다음과같이 정리하면 즉 가 됩니다. 다시말해 시작점을 정해버리면 끝점은 만에 구해낼수 있다는것이죠 ! 따라서 으로 모든 시작점을 고려하면 됩니다. 두번째 방법) 두번째 방법으로는 범위를 늘렸다 줄였다 하는 Sliding win..