[백준 17938] 퐁당퐁당2

www.acmicpc.net/problem/17938

17938번: 퐁당퐁당 2

 

이번 문제는 완전히 수학적인 사고를 통해 풀어야하는 문제이다.

저는 전체적으로 큰 로테이션인 (1 ~ 2N ~ 2)를 하나의 큰 로테이션 루틴으로 잡고 풀었다.

---

한 루틴을 돌때, 쓰이는 손의 개수는

(1 ~ 2N ~ 2) = (1 ~ 2N) + (1 ~ 2N) - 1 - 2N    이다.

(2N 과 1 은 중복되지 않기 때문!!)

 

여기서 1~2N의 총합은 (1+2N) * N이다. (가우스가 푼 방식을 이용)

게다가 이게 두개니까 2 * N * (1+2N) = 4N^2 + 2N

여기서 2N 과 1을 빼주면

한 루틴당 들어올리는 손의 개수 = 4N^2 - 1

---

한루틴을 돌때의 횟수 

1 ~ 2N ~ 2 개수를 세어보면 1~2N = 2N 번

2N-1 ~ 2 의 개수 = 2N -2 번

총 4N-2 

---

전체가 다 손을 드는 횟수 = 2N (손은 두개니까 ㅎㅎ)

T 가 입력으로 들어오면 4N-2(한 루틴의 횟수)로 나눈다

몫은 Div 라고 하겠다.

나머지는 R 이라고 하겠다

---

한 루틴을 돌때 들은 손이 모든사람은 돌고 남은 수를 알고싶으면

(4N^2 - 1 / 2N)

여기서 이 남은 손의 수를 Div 번 반복할 것이기 때문이 

(4N^2 - 1 / 2N) * Div

= Div 번 루틴을 돌 때의 손의 남은 수

---

Div 번 루틴을 돌 때의 손의 남은 수 + 남은 횟수(R)를 통해 들어야하는 손

 

여기서 실수하면 안되는게

R-1 번까지 게임을 진행하여 위치를 구하고,

R번째에서 몇명이 손을 들어야하는지를 알아야한다!

 

R-1번째까지의 손의 개수를 파악하여 R번째를 시작하기 전에 손의 위치를 알아낸다.

R번째일 때 하나씩 손을 들어가면서 손이 들리는지 알아낸다!

 

---

코드는 다음과 같다.

 

#include <iostream>

using namespace std;

int RemainPongDang(int nN,int nR)
{
	int nSum = 0;

	for(int i = 1; i < nR; i++)
	{
		if(i > 2*nN)
		{
			nSum += 4*nN - i;
		}
		else
		{	
			nSum += i;
		}
	}

	return nSum;
}

int PongDang(int nN, int nP, int nT)
{
	int nRotHand= 4 * nN * nN - 1;
	int nRotT = 4 * nN - 2;

	int nRRot = nRotHand % (2 * nN);
	int nR = nT % nRotT;

	int nHand_Pos = (nRRot * (nT / nRotT) + RemainPongDang(nN, nR)) % (2 * nN);
	int nHand_Remain = 0;

	if(nR > 2*nN)
		nHand_Remain += 4*nN - nR;
	else
		nHand_Remain += nR;
		
	for(int i = 0; i < nHand_Remain; i++)
	{
		nHand_Pos += 1;
		
		if(nHand_Pos > (2*nN))
			nHand_Pos %= (2*nN);

		if(nHand_Pos == (2*nP-1) ||  nHand_Pos == 2*nP )
			return 1;
	}
	return 0;
}

int main(void)
{
	int nN = 0, nP = 0, nT = 0;

	cin >> nN >> nP >> nT;
	
	if(PongDang(nN, nP, nT))
		cout << "Dehet YeonJwaJe ^~^" << endl;
	else
		cout << "Hing...NoJam" << endl;
	
	return 0;
}

 

여태까지 풀어본 문제중 제일 설명이 길었던 문제같다.

다른건 자료구조나 알고리즘에 맞춰서 풀어서 보통 이렇게 까지는 설명이 필요없어서 그런거같다......