[BOJ][Python]11203번 풀이

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

11203번: Numbers On a Tree

line = input().strip()
if line.isdigit():
    print(2**(int(line)+1)-1)
else:
    h, order = line.split()
    node = 2**(int(h)+1)-1
    subtract = 0
    state = ''
    if order[0] == 'L':
        subtract = 1
        state = 'L'
    else:
        subtract = 2
        state = 'R'
    node -= subtract
    for i in range(1, len(order)):
        if state == 'L':
            if order[i] == 'L':
                subtract *= 2
            else:
                subtract = subtract * 2 + 1
                state = 'R'
        else:
            if order[i] == 'L':
                subtract = subtract * 2 - 1
                state = 'L'
            else:
                subtract *= 2
        node -= subtract
    print(node)

문제 자체는 어렵지 않습니다만, 테스트 케이스 중에 입력의 오른쪽에 공백이 따라오는게 있습니다. 몇 개나 되는지 알 수 없으니 그냥 strip()으로 지워주세요(오른쪽이란 걸 아는 이유는 lstrip과 rstrip 둘 다 시도해봤고 rstrip은 통과, lstrip은 밸류 에러가 나서입니다). 아무리 해봐도 안틀렸는데 자꾸 밸류 에러가 나서 무슨 일인가 싶었네요. 그냥 split()만 가지고 안되는 이유는 order가 없이 h만 들어오는 경우가 있기 때문입니다. argument 부족으로 컴파일 에러가 날거에요. 또는 밑에서 order를 이용하는 명령들이 작동하지 않겠죠.

 

문제 접근은 명령이 L일 때와 R일 때 어떤 규칙을 가지는지 찾아내면 조건문을 작성하는 것은 비교적 쉽습니다. 제가 해봤을 때는 똑같은 명령이 연속해서 나온다면 직전의 값에 2를 곱하고 아닐 경우는 L이 먼저냐 R이 먼저냐에 따라 값이 달라진다는 것입니다. 저는 이 정도만 가지고도 충분히 문제를 풀 수 있었으니까 여기서 규칙을 더 찾는 것을 멈췄지만, 여러분이 해보신다면 저보다 훨씬 일반적으로 작성할 수 있는 규칙을 찾으실수도 있겠네요.

 

그리고 이건 도대체 왜 안되는지 찾기 위해서 계속 뒤져보다가 발견한 방법인데 신기하기도 해서 직접 구현해봤습니다. 다만 속도는 위 코드가 좀 더 빠릅니다.

line = input().strip()
if line.isdigit():
    print(2**(int(line)+1)-1)
else:
    h, order = line.split()
    ans = 1
    for i in order:
        ans *= 2
        if i == 'R':
            ans += 1
    print(2**(int(h)+1) - ans)

해당 방법은 주어진 Root부터 내림차순으로 시작해서 오른쪽에서 아래로 숫자가 작아지는 트리를 위에서부터 오름차순으로 왼쪽부터 오른쪽으로 증가하도록 노드의 위치를 변경하고, 명령을 root 부터 시행한 다음 도착한 노드를 2^(h+1)에서 뺀 것이 원래대로 진행하는 것과 결과가 같다는 내용을 기반으로한 방법입니다. 사실 감으로는 쉽게 이해가 되는게 트리는 뒤집고 과정은 그대로 진행했으니 노드를 빼주면 같은 결과가 나온다는 건 직감적으로 이해가 되는 부분이긴 합니다. 식으로도 증명할 수 있는게 왼쪽으로 갈 때는 root * 2, 오른쪽으로 갈 때는 root *2 + 1을 하는 것이니 해당 방법으로 제네럴한 형태로 만들면 증명할 수 있겠죠.