[코딩테스트][백준] 🔥 백준 5904번 "Moo 게임" 문제: Python으로 완벽 해결하기! 🔥

문제 링크

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

🕒 Python 풀이시간: 25분

n=int(input())

s="moo"
dp=[0]
dp.append(3)
index=1
while True:
    dp.append(dp[index]+1+index+2+dp[index])
    if dp[-1]>=n:
        break
    index+=1

nowIndex=len(dp)-1
while True:
    if nowIndex==0:
        print(s[n-1])
        break
    if dp[nowIndex-1]<n<=nowIndex+2+dp[nowIndex-1]:
        if n==dp[nowIndex-1]+1:
            print('m')
            break
        else:
            print('o')
            break
    if dp[nowIndex-1]<n:                                            
        n-=nowIndex+2+dp[nowIndex-1]
    nowIndex-=1

Moo 게임: N번째 글자 찾기! 🎮🔤

Moo는 술자리에서 할 수 있는 게임인데 이 외치는 규칙이 점화식을 이룬다. 이 때, N이 주어질 때, N번째 오는 글자가 무엇인지 구하는 문제이다. 점화식이기 때문에 간단히 DP로 접근하였다.

먼저 현재의 N이 포함되는 K를 구한다. 즉, 몇 번째 수열에 포함되어 있는지를 구하는 것이다. 이는 단순히 글자 수를 가지고 규칙대로 늘려나가되 포함할 때까지만 늘려나가면 된다. 그런 다음 이제 분할 하여 접근한다. 만약 현재 찾는 수열이 0번째 수열이라면 그대로 출력한다. 그렇지 않고 현재 수열의 가운데에 위치할 경우라면 k-1번째 수열 바로 다음번째 오는 글자라면 M을 나머지라면 o를 출력한다. 마지막으로 그 이외에 존재한다면 앞과 뒤가 똑같기 때문에 앞쪽을 선택하여 현재의 n, 즉 몇번째 오는지에 대해서 뒤쪽에 있다면 앞쪽에 있는 index와 같은 취급을 해준다. 그리고 현재 수열은 k-1번째 수열로 이루어져있기 때문에 현재 수열의 index에서 -1을 해준다.

이렇게 Python으로 백준의 "Moo 게임" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊