[백준-파이썬] 5904: Moo 게임

ㅠㅠ 분할 정복....5개월 전에 스터디 문제였는데 그때 뭔가 이해는 된 것 같은데 못 풀었다..
분할 정복 문제들은 어떻게 쪼개지는지 까지는 대충 아는 것 같은데, 그걸 어떻게 코드로 구현할지 막막하다.ㅠㅠ
그래도 풀면 나아지겠지 !?!
친구의 도움을 받아서 푼 Moo 게임 !!

문제 보러 가기

풀이 🌸

1. moo() 함수 부분!! 일단 미리 각 k일 때 moo 수열의 길이를 구해서 m_list에 저장했다. N이 10의 9승까지 된다고 했는데, 그걸 포함하는 moo 수열의 k는 30이다. (S(30)이 10의 9승보다 길게 된다.) 그래서 moo(30)을 구하면 된다. 

2. N과 같거나 큰 S(k)의 길이를 찾아준다. 그럼 moo 수열의 N번째 알파벳을 찾기 위해서는 Moo수열에서 S(k)를 봐주면 된다는 뜻이니까!! k-1을 idx로 삼아서 sol() 함수를 시작한다.

3. sol() 함수 부분!!
idx가 -1라면, 즉 S(0)인 상황이라면, n이 1이면 'm', 그게 아니라면 'o'이다.

idx가 그것보다 크다면, 3등분해서 n이 어디 속하는지에 따라서 다르게 처리한다. moo 수열을 보면 3등분해서 볼 수 있다. (위에 이미지에서 남색 네모 기준으로 볼 때, 보라 색으로 나눈 것처럼 3등분 할 수 있다) S(k)가 있으면, 왼쪽 S(k-1)인지, o가 k+2 개인 수열 부분인지, 오른쪽 S(k-1)부분인지. 이것에 따라서 다르게 처리해줬다.

이 셋 중 어디에 속하는지는 idx를 통해서 알 수 있다. n <= S(idx)의 길이라면, 왼쪽에 속한다. S(idx)의 길이 < n <= S(idx)의 길이 + (o가 k+2개인 수열의 길이)라면 가운데 속한다. 그것보다 크다면 오른쪽에 속한다.
3-1. 만약 o가 k+2개인 수열 부분이라면, 그 수열의 맨 앞일 때만 m이고 그게 아니라면 o이다. 바로 알 수 있으니까 바로 리턴해준다.
3-2. S(k-1) 부분이라면 또 sol 함수로 들어간다. 들어갈 때, n은 원래 n에서 적당한 수를 빼준 후에 들어간다. n을 구할 때 만약 왼쪽 S(k-1)이라면 아무것도 빼줄 필요가 없고, 오른쪽 S(k-1)라면 S(k-1)의 길이와 o가 k+2개인 수열의 길이를 빼주고 들어가야 한다.

예시 🧐

만약 N이 20이라고 가정하자. S(1)의 길이는 10, S(2)의 길이는 25이다. N의 알파벳을 구하려면 S(2)를 봐주면 된다. 근데 우리는 그것보다 1작은 걸 idx로 삼았으니까 idx가 1인 상태로 sol함수에 들어간다.

n=20, idx=1인 상황) 20은 S(2)의 어느 부분에 속하게 될까? 오른쪽 부분에 속하게 된다. 그래서 sol(n(idx+4)-10, idx-1) 식에 해당하게 된다.

n=5, idx=0인 상황) 5는 S(1)에서 어느 부분에 속할까? 가운데 부분에 속하게 된다. 그런데 가운데에 있는 글자 중에 첫번째 글자가 아니므로 o을 리턴한다.

코드 👩‍💻

N = int(input())


def moo(n):
    if n == 0:
        m_list[n] = 3
        return 3
    m_list[n] = moo(n - 1) * 2 + n + 3
    return m_list[n]

m_list = [0] * 31

def sol(n, idx):
    if idx == -1:
        if n == 1:
            return 'm'
        return 'o'
    tmp = m_list[idx]

    if n <= tmp:
        return sol(n, idx - 1)
    elif n <= tmp + idx + 4:
        if n == tmp + 1:
            return 'm'
        return 'o'
    else:
        return sol(n-(idx+4) - tmp, idx- 1)

if N == 1:
    print('m')
else:
    moo(30)
    idx = 0
    for i in range(30):
        tmp = m_list[i]
        if N >= tmp:
            idx = i
        else:
            break

    ans = sol(N, idx)
    print(ans)