관리 메뉴

커리까지

백준 5904번 Moo게임 파이썬 본문

알고리즘/풀이

백준 5904번 Moo게임 파이썬

목표는 커리 2021. 3. 18. 19:49
728x90
SMALL

문제

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번째 글자를 출력한다.

예제 입력 1

11

예제 출력 1

m

백준에 올라와 있는 답안

g=lambda i:(i<<2)-bin(i).count('1')
i=int(input())-1
n=max((i//4)-9,0)
while g(n)<i:n+=1
print('om'[g(n)==i])
  • 런타임 오류와 메모리 초과 늪에서 나오지 못해서 답안을 봤다.
  • 이 답안을 공부해봐야겠다. 정말 대단한 분이다.
728x90
LIST
Comments