1. 문제
5904번: Moo 게임
Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다. Moo 수열은 길이가 무한대이며, 다음과 같이 생겼다. m o o m o o o m o o m o o o
www.acmicpc.net
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번째 글자를 구하는 프로그램을 작성하시오.
2. 풀이
1. 길이로 몇 번째 수열인지 알아낸다.
2. 전체 길이, 가운데 길이(root)를 이용해서 앞부분 길이를 알아낸다.
3. 만약 앞부분에 속한다면(front<=N) 가운데 길이를 1 줄이고 전체길이를 앞부분길이로 바꿔서 재귀호출한다.
4. 뒷부분에 속한다면(front+root>N) N에서 front+root를 뺀 후 moo(front,root-1)을 호출한다.
5. 가운데 부분에 속한다면 N에 front를 빼고 끝낸다.
6. 함수가 끝난 후 N값이 1이라면 m, 그 나머지는 o를 출력한다.
import java.io.*;
public class BOJ_5904_Moo게임 {
static int N;
public static void main(String[] args) throws IOException {
N = Integer.parseInt(new BufferedReader(new InputStreamReader(System.in)).readLine());
//몇번째 수열인지 알아내기
int len = 3;
int root = 3;
while(N>len){
len = len*2+(++root);
}
//함수호출
moo(len,root);
//결과
if(N==1) System.out.println('m');
else System.out.println('o');
}
public static void moo(int len, int root){
//앞부분 길이
int front = (len-root)/2;
if(front>=N){//N이 앞부분에 속한다면
moo(front,root-1);
}
else if(front+root<N){//N이 뒷부분에 속한다면
N-=(front+root);
moo(front,root-1);
}else{//N이 중간부분에 속한다면
N-=front;
}
}
}
3. 결과
'코딩테스트 > BOJ' 카테고리의 다른 글
[BOJ] 1562 계단수 - JAVA (0) | 2023.02.19 |
---|---|
[BOJ] 1700 멀티탭 스케줄링 - JAVA (0) | 2023.02.18 |
[BOJ] 11000 강의실 배정 - JAVA (0) | 2023.02.15 |
[BOJ] 1744 수 묶기 - JAVA (0) | 2023.02.14 |
[BOJ] 11660 구간 합 구하기 - JAVA (0) | 2023.02.13 |
댓글