문제

23250번 하노이 탑 K

풀이

첫번째 풀이

별 의심 없이 원판을 옮기는 과정을 모두 print하는 코드에서 모두 print하지 않고 k에서 1씩 줄여가며 k가 0이 될 때만 print를 시키는 코드를 생각했었다.

첫번째 코드

n,k = map(int,input().split())
def f(n, a,c,b):
  if n==0: return None
  f(n-1,a,b,c)
  l[0] -= 1
  if l[0]==0:
    print('%d %d' %(a,c))
    exit(0)
  f(n-1,b,c,a)
l=[k]
f(n,1,3,2)

문제점

k까지만 돌고 코드가 종료되도록 해도 시간초과가 떴다. 재귀를 정직하게 다 돌면 안된다는 것을 깨달았다.

해결 방안

재귀를 돌지 않고 n개의 원판을 옮기는 데 걸리는 횟수가 2n-1 번 이라는 걸 사용하여 재귀를 돌지 않고 k를 줄이도록 하였다.

코드

n,k = map(int,input().split())
def f(n, a,c,b):
  if n==0: return None
  
  if l[0]-2**(n-1)+1<=0:f(n-1,a,b,c)
  else: l[0]=l[0]-2**(n-1)+1
  l[0] -= 1
  if l[0]==0:
    print('%d %d' %(a,c))
    exit(0)
  if l[0]-2**(n-1)+1<=0:f(n-1,b,c,a)
  else: l[0]=l[0]-2**(n-1)+1
l=[k]
f(n,1,3,2)

하노이 탑 재귀의 핵심 부분에서

def f(n,a,c,b):
	f(n-1,a,b,c)
    print('%d %d' %(a,c))
    f(n-1,b,c,a)

f(n-1,...)에서 2n-1 번의 이동이 발생한다는 것만 처리해주면 굳이 이 함수를 타고 들어갈 필요가 없다. k가 2n-1 번보다 작아서 이 함수를 타고 들어가야만 우리가 원하는 이동이 발생할 때를 제외하고는 함수를 return하지 않고 k의 크기만 줄여준다