[BOJ] 15721 번데기

문제

중앙대학교 소프트웨어학부에 새로 입학한 19학번 새내기 일구는 새내기 새로 배움터에 가서 술게임을 여러 가지 배웠다. 그 중 가장 재미있었던 게임은 바로 번데기 게임이었다.

번데기 게임의 규칙은 다음과 같다. ‘뻔 – 데기 – 뻔 – 데기 – 뻔 – 뻔 – 데기 – 데기’ 를 1회차 문장이라고 하자. 2회차 문장은 ‘뻔 – 데기 – 뻔 - 데기 – 뻔 – 뻔 – 뻔 – 데기 – 데기 – 데기’가 된다. 즉 n-1회차 문장일 때는 ‘뻔 – 데기 – 뻔 – 데기 – 뻔(x n번) – 데기(x n번)’이 된다. 하이픈 사이를 지날 때마다 순서는 다음 사람으로 넘어간다. 원을 돌아 다시 일구 차례가 와도 게임은 계속 진행된다.

일구와 동기들, 그리고 선배들을 포함한 사람 A명이 다음과 같이 원으로 앉아 있다고 가정하자. 

일구가 0번째이고, 반 시계 방향으로 번데기 게임을 진행한다. T번째 ‘뻔’ 또는 ‘데기’를 외치는 사람은 위 원에서 몇 번 사람인지를 구하여라. (새내기는 10000번째가 되는 순간 시체방에 가기 때문에 T는 10000이하의 임의의 자연수이다.)

입력

첫째 줄에 게임을 진행하는 사람 A명이 주어진다. A는 2,000보다 작거나 같은 자연수이다.

둘째 줄에는 구하고자 하는 번째 T가 주어진다. (T ≤ 10000)

셋째 줄에는 구하고자 하는 구호가 “뻔”이면 0, “데기”면 1로 주어진다. 

출력

첫째 줄에 구하고자 하는 사람이 원탁에서 몇 번째에 있는지 정수로 출력한다. 

해결 방법

- main: 지금 순서부터 차례대로 직접 세어본다. 

이때 번, 데기의 순번을 저장하기 위해 2개짜리 int 배열(count)을 둔다. 그리고 원하는 단어의 순번이 T가 될 때까지 반복문(1)을 돈다. 

한번의 round에서는 번-데기-번-데기-번-번-데기-데기 라는 문자열이 늘어나게 되는데 항상 번-데기-번-데기의 4개 단어의 반복 후 round + 1개 만큼 번을 반복, 데기를 반복하게 된다. 따라서 (1) 안에서 4개 단어에 대한 반복문, 나머지에 대한 반복문으로 나누어서 round를 처리한다. 

순수하게 반복문을 모두 돌면 연산이 너무 많아지므로 한 라운드를 다 돌아도 T에 미치지 못한다는 것을 for문 들어가기 전에 확인하고 미치지 못한다면 count의 횟수만 증가시키고 다음 라운드로 넘어가고 T 이상이 된다면 for문을 통해 T번째를 찾도록 한다. 

 

package bruteForceSearch;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class boj_15721 {

	static int A, T, N;

	static void input() {
		FastReader scan = new FastReader();
		A = scan.nextInt();
		T = scan.nextInt();
		N = scan.nextInt();
	}

	public static void main(String[] args) {
		input();
		int[] count = {0, 0};
		int round = 1;

		while (count[N] != T) {
			if (count[0] + round + 3 < T) {
				count[0] += round + 3;
				count[1] += round + 3;
				round++;
				continue;
			}
			for (int i = 0; i < 4; i++) { // 번-데기-번-데기
				if (i % 2 == 0) {
					count[0]++;
				} else {
					count[1]++;
				}
				if (count[N] == T) {
					System.out.println((count[0] + count[1] - 1) % A);
					return;
				}
			}

			for (int i = 0; i < (round + 1) * 2; i++) { //번-번-데기-데기
				if (i < round + 1) {
					count[0]++;
				} else {
					count[1]++;
				}
				if (count[N] == T) {
					System.out.println((count[0] + count[1] - 1) % A);
					return;
				}
			}
			round++;
		}
		System.out.println(count[N] % A);
	}
}