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 windows 기법을 사용하면 쉽게 답이 나옵니다.

즉 1부터 쭉 더해나가다가 합이 N보다 더 커지면 1부터 하나씩 빼나가는것이죠 .
이는 코드를 보시면 더욱 직관적으로 아실수 있을겁니다.

start = 0; sum = 0;

for(i=1;i<=n;i++) 

{
	sum+=i;

	while(sum>n) sum-= ++start;
	if(sum==n) cnt++; 

 } 


이방법 또한 시간복잡도는     입니다.


2. Ship Travelling (http://koistudy.net/?mid=prob_page&NO=503)

이문제와 관련이 큰 문제가 APIO 2009 문제인 ATM문제입니다.
ATM과 해법이 동일하다고 할수 있는데요.

위 문제에서 본다면
우선 S에서 T까지의 최대한 많은 정점을 거쳐가는 경로를 찾아야 됩니다.
각 정점은 여러번 방문할수있음으로 S에서 T까지의 경로도중 현재경로를 포함하는 사이클이 존재한다면, 그 사이클을 다 돌고 와서 다른 정점으로 이동하는것이 더 이득이 됩니다.

그렇다면 그런 사이클들을 어떻게 판별할까요?
해답은 SCC(strongly connected component) 입니다.

SCC를 찾아서 강 정점에 가중치를 SCC에 포함된 정점의 갯수로 둡니다.
그렇다면 문제는 쉬워졌습니다.

S->T까지 가장많은 정점을 거쳐 가는 경로를 찾는것은 DAG(Directed acyclic graph) 에서 최장경로를 찾는 문제로 귀결되었습니다.

따라서 이 문제는  만에 해결 될 수 있습니다.
 


3번과 4번은 둘다 다이나믹 프로그레밍 문제입니다. 
간단히 다이나믹 정의만 남길테니 점화식을 알아서 찾아보세요 ^^


3.Cutting Confectionery (http://koistudy.net/?mid=prob_page&NO=504)

D1(i,j) = i번째 조각을 예찬이에게 줄때, 예찬이의 총조각은 j조각이며 태양이의 조각은 i-j조각
D2(i,j) = i번째 조각을 태양이에게 줄때, 예찬이의 총조각은 j조각이며 태양이의 조각은 i-j조각

점화식을 세워보시면 굳이 이차원 배열을 쓸 필요없이 일차원으로만 구현이 가능하다는것을 아실수 있으실겁니다.

시간복잡도는  입니다.

4.  Comeback vault 101 (from Fallout3) ( http://koistudy.net/?mid=prob_page&NO=505 )


우선 (1,1) -> (N,M) -> (1,1)으로 돌아오는 경로는 (1,1)에서 (N,M)까지의 경로 2개를 찾으면 된다는것을 확인하자.

 
그렇다면, 우선 N*M Matrix를  위와같이 대각선을 긋으면 한 대각선은 2개의 경로에서 각각 한번씩 총 두번지난다는것을 알수 있습니다. 

왼쪽 위부터 대각선에 번호를 메긴다면 총 1~H+W-1로 메길수 있습니다.

D(i,j,k) = i번째 대각선에서 2개를 지나가는데 j번째 행과 k번째 행을 지나갈때의 최적값

시간복잡도는  만에 해결 될 수 있습니다.