0910_algorithm_14562_태권왕

문제 : https://www.acmicpc.net/problem/14562

초기 구상단계

1. DFS 적용해서 재귀호출을 이용해서 풀자!
2. Backtracking은 처음부터 적용하지 말고 단계로 나가보자
3. step으로 표현하면 cnt는 자동!, 탐색하면서 최소값 갱신하면 되겠다.
   case A > N += N / M += 3 > i = 0
   case B > N += 1 > i = 1

풀이

def dfs(step, S, T):
	global mini
    if S == T:
    	if step <= mini:
        	mini = step
            return
	else:
    	for i in range(2):
        	if i == 0:
            	S += S
                T += 3
            else:
            	S += 1
            dfs(step + 1, S, T)
            

• 초기에 생각하고 작성했던 재귀함수 형태.
• sample에서 두번째와 네번째 경우만 맞고 다 틀려버린 함수
  • Debuging을 해보니 S가 함수를 빠져나오면 그 전 값으로 돌아갈 줄 알았지만 열어보니 한 재귀함수 벗어나도 값이 그대로였던 점
  • update되는 S와 T 값 중 S가 이미 T를 넘어서버리는 경우 계속해서 돌아가게 되는 점

최종 코드

def dfs(step, S, T):
    global mini
    if S == T:
        if step <= mini:
            mini = step
            return
    elif S > T:
        return
    else:
        for i in range(2):
            if i == 0:
                S += S
                T += 3
                dfs(step + 1, S, T)
                S -= S >> 1
                T -= 3
            else:
                S += 1
                dfs(step + 1, S, T)
                S -= 1


for tc in range(int(input())):
    S, T = map(int, input().split())

    mini = 1000
    dfs(0, S, T)
    print(mini)

• S -= S >> 1 : 이 부분은 비트 연산자를 이용한 몫 연산이 //보다 더 빠르다는 짤막한 지식을 교수님께 들은 적이 있어서 사용하는 방법
• 다른 사람들 코딩을 보면 굳이 재귀함수에 argument를 많이 안넣던데 왜 그런지 더 공부 해야겠다.