일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 백준 #알고리즘 #파이썬 #코딩테스트
- css #웹 #생활코딩
- Dijkstra
- PYTHON
- 프로그래머스 #파이썬 #코딩테스트 #알고리즘
- java #자바 #나동빈
- react #리액트 #동빈나
- 프로그래머스
- 자바 #java
- dp
- 프로그래머스 #파이썬 #알고리즘 #코딩테스트
- 다이나믹프로그래밍
- 다익스트라
- 백준 #파이썬 #알고리즘 #코딩테스트
- DFS
- 파이썬 #알고리즘 #코딩테스트 #프로그래머스
- css #생활코딩 #웹
- react #리액트 #동빈나 #나동빈 #유튜브강의
- 파이썬
- 파이썬 #백준 #알고리즘 #코딩테스트
- BFS
- 백트랙킹
- 백준
- java #자바 #생활코딩
- java #자바 #동빈나
- java #자바
- 투포인터
- 알고리즘
- 코딩테스트
- 재귀
Archives
- Today
- Total
커리까지
백준 5904번 Moo게임 파이썬 본문
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
'알고리즘 > 풀이' 카테고리의 다른 글
프로그래머스 2019 KAKAO 오픈채팅방 파이썬 (0) | 2021.03.20 |
---|---|
백준 2178번 미로 탐색 파이썬 (0) | 2021.03.19 |
백준 1021번 회전하는 큐 파이썬 (0) | 2021.03.17 |
백준 17952번 과제는 끝나지 않아! 파이썬 (0) | 2021.03.16 |
백준 11725번 트리의 부모 찾기 파이썬 (0) | 2021.03.10 |
Comments