[BOJ / Python] 5904 Moo 게임

🧩 문제 : 5904번

💪🏻 해결 방법 

1️⃣ 재귀로 풀기 

1. 입력 받은 N으로 K구하기

2. Moo 수열 S(K) 만들기

3. S(K)의 N번째 글자 출력하기

 

전체 코드 - 메모리 초과

import sys

# 입력
n = int(sys.stdin.readline())  # 출력할 n번째 자리수

result = []  # Moo 수열 S(k)
size = 0  # Moo 수열의 크기
k = 0  # Moo 수열에 사용될 변수


# moo 수열 S(k)를 만드는 함수
def moo(x):
    if x < 0: return ""
    mid = "m" + ("o" * (x + 2))
    result.append(moo(x - 1))
    result.append(mid)
    result.append(moo(x - 1))


# moo 수열의 길이를 구하는 함수
def moo_size(x):
    if x < 0: return 0
    first_and_last = moo_size(x - 1)
    mid = x + 3
    size = int(2 * first_and_last) + int(mid)
    return size


for i in range(28):
    length = moo_size(i)
    if length >= n:
        k = i
        break

moo(k)
result = list(filter(None, result))
result = "".join(result)

if n > 1: print(result[n - 1])

 

2️⃣ 재귀 + 분할정복으로 풀기 

 

1. 입력 받은 N으로 K구하기

 

왼쪽 S(k-1)부분에 N이 존재하면 사실상 S(k-1)의 N번째 문자를 찾는 것과 같다.

오른쪽 S(k-1)부분에 N이 존재하면 S(k-1)의 (N-S(k-1)의길이-가운데부분길이)번째 문자를 찾는 것과 같다.

가운데 부분에 N이 존재한다면 바로 N번째 문자를 알 수 있다.

 

정답 코드 

# 참고 : https://tesseractjh.tistory.com/101
import sys

n = int(sys.stdin.readline()) # 입력

def moo(n, k, moo_size):
    size = (moo_size - (k+3)) // 2 # s(k-1)의 길이
    
    # 왼쪽 s(k-1)에서 찾는 경우, s(k-1)에서 찾는 것과 같은 결과
    if n <= size:
        return moo(n, k-1, size)
    
    # 오른쪽 s(k-1)에서 찾아야 하는 경우, 오른쪽 파트에 맞춰 n 과 s_k_i 계산
    elif n > size + (k+3):
        return moo(n - (size + k+3), k-1, size)
    
    # 가운데 파트에서 찾는 경우, 첫 글자 인덱스 확인
    else: 
        if n == size + 1:
            return "m"
        else:
            return "o"


moo_size, k = 3, 0
while n > moo_size:
    k += 1
    moo_size = 2 * s_k + (k + 3) # s(k)의 총 길이
    
print(moo(n, k, moo_size))

 

🎁 성공!