[백준 C++] 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로 주어진다.

출력

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

예제 입력 / 출력

// 예제 입력 1
8
2
0

// 예제 출력 1
2

// 예제 입력 2
4
6
1

// 예제 출력 1
3

힌트

예를 들어 7명이 있고, 16번째 등장하는 “뻔”을 부른 사람의 번호를 알고 싶다면 입력은 7 16 0이다. 4명이 있고 6번째 등장하는 “데기”를 부른 사람의 번호를 알고 싶다면 입력은 4 6 1이며, 이때 출력 값은 반 시계 방향으로 3번째 있는 사람이므로 3을 출력한다.

알고리즘
뻔-데기-뻔-데기-뻔(xn번)-데기(xn번)이므로 바깥 반복문은 뻔-데기-뻔-데기-뻔(xn번)-데기(xn번)를 도는 반복문, 안쪽 반복문은 뻔(xn번)-데기(xn번)를 돌도록 해서 사람 수도 count해 나머지 나눗셈으로 구해준다.

#include <iostream>

using namespace std;

int main(void) {

	int A, T;
	bool is_degi;
	int bbun = 0, degi = 0, n = -1;

	cin >> A >> T >> is_degi;

	int cnt = 2;
	while (1) {

		for (int i = 0; i < 2; i++) {
			bbun++; n++;
			if (!is_degi && bbun == T) {
				cout << n % A;
				return 0;
			}
			degi++; n++;
			if (is_degi && degi == T) {
				cout << n % A;
				return 0;
			}
		}

		for (int i = 0; i < cnt; i++) {
			bbun++; n++;
			if (!is_degi && bbun == T) {
				cout << n % A;
				return 0;
			}
		}

		for (int i = 0; i < cnt; i++) {
			degi++; n++;
			if (is_degi && degi == T) {
				cout << n % A;
				return 0;
			}
		}

		cnt++;
	}
	
}