[PYTHON] 백준 5904 - Moo 게임

성능 요약

메모리: 113112 KB, 시간: 112 ms

분류

분할 정복, 재귀

문제 설명

Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다.

Moo 수열은 길이가 무한대이며, 다음과 같이 생겼다.

m o o m o o o m o o m o o o o m o o m o o o m o o m o o o o o

Moo 수열은 다음과 같은 방법으로 재귀적으로 만들 수 있다. 먼저, S(0)을 길이가 3인 수열 "m o o"이라고 하자. 1보다 크거나 같은 모든 k에 대해서, S(k)는 S(k-1)과 o가 k+2개인 수열 "m o ... o" 와 S(k-1)을 합쳐서 만들 수 있다.

S(0) = "m o o"
S(1) = "m o o m o o o m o o"
S(2) = "m o o m o o o m o o m o o o o m o o m o o o m o o"

위와 같은 식으로 만들면, 길이가 무한대인 문자열을 만들 수 있으며, 그 수열을 Moo 수열이라고 한다.

N이 주어졌을 때, Moo 수열의 N번째 글자를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 109)이 주어진다.

출력

N번째 글자를 출력한다.

---

아이디어, 문제풀이

• 분할정복으로 풀어야 하는 문제
• 분할 조건을 확실하게 정하는게 필요
• 배열의 길이 → n과 같은 선상에 있다고 생각하면 → 수식으로 표현할 수 있다는 의미

---

TROUBLE SHOOTING

• 첫번쨰로 아이디어를 실제로 구현하는 과정이 어려웠다. 이 문제는 결국 나오는 m, o 중 출력값을 정해야 하는데, 길이를 기준으로 분할정복을 해야하는지, 아니면 k 를 기준으로 분할해야하는지가 햇갈렸던것 같다.

• 위의 내용과 이어지는 부분인데, 실제로 처음에는 길이를 받아오는 재귀함수를 구현했었다.

  def n_length(k):
      if k == 0:
          return 3
      else:
          return (n_length(k-1) + 1 + k+2 + n_length(k-1))

  이 재귀함수를 통해 n이 몇번째 k에 있는지 확인할수 있는데, 여기서 코드를 구현하려 하니 정말 막막했다.

  그래서 다시 문제를 확인했고, k를 활용해서 분할정복을 해야겠다는 생각을 했다.

  def fun(n, k):
      if k == 0:
          if n == 1:
              return "m"
          elif n == 2:
              return "o"
          elif n == 3:
              return "o"
  
      #첫번째 s(k-1)에 위치할때
      if n <= n_length(k - 1):
          return fun(n, k - 1)
      
      # 1+ k+2 구간에 위치할때
      elif n == n_length(k - 1) + 1: # s(k-1)
          return "m"
      elif n <= n_length(k - 1) + k + 3:
          return "o"
      
      #두번째 s(k-1)에 위치할때
      else:
          return fun(n - (n_length(k - 1) + k + 3), k - 1)

  이 재귀문 자체를 구현하는건 어렵지 않았는데, 문제는 시간초과였다.
  

• 문제풀이와 리뷰를 해보며 내가 내린 결론은, 재귀문이 두번 겹쳐있다는 점이다. chat gpt의 설명도 따로 첨부하겠지만, 시험 당시에는 위쪽에 내가 만든 길이 관련된 재귀문을 다른 방식으로 구현해야 된다는 결론을 내렸던것 같다.

  #k 가 0 일때 len은 3 / 초기값
  k = 0
  length_list = [3]
  
  while length_list[-1] < n:
      k += 1
      next_length = length_list[-1] + 1 + k + 2 + length_list[-1]
      length_list.append(next_length)

  실제로 구현한 코드. 처음엔 재귀가 아니면 안된다라고 생각했는데, 결국 k의 위치를 찾는게 주된 목적 이였기 때문에 어렵지 않게 구현할 수 있었다.
  

---

코드

#https://www.acmicpc.net/problem/5904
#Moo 게임
#5904

import sys
input = sys.stdin.readline

n = int(input())

#재귀적 표현이 아닌 반복문으로 풀이하는법

#k 가 0 일때 len은 3 / 초기값
k = 0
length_list = [3]

while length_list[-1] < n:
    k += 1
    next_length = length_list[-1] + 1 + k + 2 + length_list[-1]
    length_list.append(next_length)

def fun(n, k, length_list):

    #탈출조건
    if k == 0:
        if n == 1:
            return "m"
        elif n == 2:
            return "o"
        elif n == 3:
            return "o"

    #첫번째 s(k-1)에 위차할경우
    if n <= length_list[k - 1]:
        return fun(n, k - 1, length_list)
    
    #가운데 1+ k+2 구간에 위치할경우
    elif n == length_list[k - 1] + 1:
        return "m"
    
    elif n <= length_list[k - 1] + k + 3:
        return "o"
    
    #두번째 s(k-1) 에 위치할경우
    else:
        return fun(n - (length_list[k - 1] + k + 3), k - 1, length_list)

print(fun(n, k, length_list))