백준 23250 하노이 탑 K

문제

https://www.acmicpc.net/problem/23250

23250번: 하노이 탑 K

 

하노이탑은 다음과 같은 기본로직에서 출발한다.

원판이 1~N개 있을때 

1. 1~N-1 묶음을 1번에서 2번막대로 옮긴다.

2. N번 원판을 1번에서 3번으로 옮긴다.

3. 1~N-1 묶음을 2번에서 3번으로 옮긴다.

따라서 원판이 N개인 하노이탑을 옮기는 횟수 F(N) = F(N-1) + 1 + F(N-1) = 2^N - 1이다.

이것을 기본 하노이탑 코드로 제출할시 2^60이란 어마무시한 숫자를 감당못하므로 시간이 초과날 것이다.

F(N) = T라고 하고 F(N-1)이 T'이라 하면,

1번째에서 T'-1번까지는 1~N-1묶음을 1번에서 2번막대로 옮기는 과정이다.

T'번째는 N번원판을 1번에서 3번으로 옮기는 과정이다.

T'+1번째~T번째는 1~N-1묶음을 2번에서 3번으로 옮기는 과정이다.

만약에 1<= K <=T'-1이라하자.

그러면 T'+1~T번째 움직임을 굳이 볼 필요가 있을까?

마찬가지로 K == T'이라면 or T'+1 <= K <= T라면 굳이 다른 과정을 볼 필요가 있을까?

그럴 필요 없다.

F(N) = F(N-1) + 1 + F(N-1)이므로, log2(2^N-1)의 복잡도로 빠르게 계산할 수 있다.

절반의 움직임을 날리기 떄문이다.

 

필요한 정보는 다음과 같다.

 

getTot(int N) 또는 cnt[N]: N개의 원판묶음을 옮기는데 필요한 총 움직임 수

getTot은 2^N-1을 넣어주고 cnt의 원소도 마친가지로 구해준다.

 

solve()함수

solve함수의 param

s1: 시작 막대, s2:경유 막대, s3:목적 막대

우린 원판묶음을 s1->s3로 옮길 것이다.

start,end: 현재 보고 있는 움직임의 범위

cnt: 현재 옮기는 원판 묶음의 크기

 

func solve(int s1,int s2,int s3,ll start,ll end,int scale){
	ll half = cnt[scale-1];
    ll part1 = start + half - 1;
    ll mid = start + half;
    ll part2 = start + half + 1; 
    if (K <= part1){
    	return solve(s1,s3,s2,start,part1,scale-1);
    } else if (K == mid{
    	return [s1,s3]; // result
    } else if (K >= part2{
    	return solve(s2,s1,s3,part2,end,scale-1);
    }
}
print(solve(1,2,3,1,cnt[N],N);