[boj 16953][Python] a to b

문제 링크

접근

모든 경우에 대해서 다 체크해보면 되겠다고 생각했다. 이렇게 생각한 이유는 우선, 목표로 하는 b값의 최대가 10^9 이다. 어떻게 보면 큰 수이지만, 제곱으로 접근할 수 있어서 괜찮다고 생각했다. 2^40 이 10^8과 유사하니 최대 50번 정도 걸릴 거라고 판단했다.

노트에 가지 그림을 그렸다. 테스트 케이스에 대해서 2에서 출발해서 162가 되기까지 어떤 과정을 거치는지 체크한다.

가지 그림을 코드에서는 어떤 식으로 구현할 것인가? 여러 방법이 있겠지만 나는 딱 떠오르는 게 재귀라서 재귀로 구현하였다.

파이썬 재귀 함수의 return None 문제

a, b = map(int, input().split())

def recursion(result, goal, depth):
    if result > goal:
        return -1
    elif result == goal:
        print(depth)
        return depth
    recursion(result*2, goal, depth+1)
    recursion(result*10+1, goal, depth+1)

print(recursion(a, b, 0))

이것은 내가 처음에 작성한 코드이다. 우선은 문제에서 원하는 바가 depth +1인데 이걸 빼먹었다.

그것보다 더 큰 문제는 마지막의 print(recursion())에서 None 이 나온다는 것이다. 테스트를 위해 집어넣은 print(depth) 에서는 정상적으로 나오는다. 이런 점 때문에 파이썬에서 재귀함수 사용 시에는 주의를 기울여야 한다.

이 문제는 이전에 포스팅으로 남긴 적도 있는데, 이번에 다시 알아보았다.

생각하기로는 recursion의 leaf에서 -1 혹은 depth가 return 되니까 그게 최종 결과로 남을 것 같다. 그러나 실제로 재귀는 스택 구조. 그러므로 스택의 가장 위에서 -1 혹은 depth가 return 되는데, 그 다음으로 남은 스택들에서는 None이 return 된다는 것이다. (파이썬에서 명시적 return 하지 않은 경우 None 이 return 된다.) 마지막 결과는 덮어씌워져 결국 return 이 출력되는 것이다.

이를 고치기 위해, 마지막으로 리턴할 값을 전역변수로 선언하고, 함수 내에서 전역변수에 접근하도록 한다. (실제로 개발 할 때 이런 방법을 쓰기는 위험하겠지만, 오로지 문제 풀이를 위한 것이기 때문에...)

a, b = map(int, input().split())
rst = -1

def recursion(result, goal, depth):
    if result > goal:
        return
    elif result == goal:
        global rst
        rst = depth+1
        return
    recursion(result*2, goal, depth+1)
    recursion(result*10+1, goal, depth+1)

recursion(a, b, 0)
print(rst)

성공!

그렇다면 다른 언어는 어떨까?

파이썬 재귀 함수에서 의도하지 않은 None 이 return되는 현상은, 파이썬이 꼬리 재귀 최적화를 지원하지 않기 때문이다.

이것을 지원하는 언어로 다시 작성해보았다.

#include <stdio.h>
#pragma waring (disable: 4996)

int recursion(int result, int goal, int depth);

int main(){
    int a, b;
    scanf("%d %d", &a, &b);
    printf("%d", recursion(a, b, 0));
    return 0;
}

int recursion(int result, int goal, int depth){
    if (result>goal) return -1;
    else if (result == goal) {
        printf("%d", depth);
        return depth;
    }
    recursion(result*2, goal, depth+1);
    recursion(result*10+1, goal, depth+1);
}

이것은 이 포스팅의 첫번째 코드처럼, 재귀 값을 바로 print 한 것이다. 이렇게 하면 결과가 -1 이라고 나온다. return depth 위에서 출력하여 검사해보니 depth 는 확실히 찍힌다.

이렇게 되는 이유는, 스택의 최상단에 있는 것이 return depth가 아니기 때문이다. 가지 그림을 그려 봤으면 알겠지만, 162라는 답이 도출된 후의 depth에서도 goal과 같은지 평가가 이루어지며 가지치기(return -1)가 되기 때문이다.

이번 포스팅 끝!