[BOJ/26154번] 한양 가왕 (C++/애드 혹)

개요

https://www.acmicpc.net/problem/26154

26154번: 한양 가왕

GoldⅡ 

애드 혹  + 구현 문제

출제자의 추천으로 풀게 된 문제 ! (M** 보고 있냐)

 

본문

M이 10억 인 것만 봐도 단순 탐색 시 시간초과가 난다.

N을 3으로 잡고 한 번 돌려보았다.

규칙에 따른다면 라운드별로 아래와 같이 진행된다.

라운드 / 방 번호	1		2		3		4		5		6
1	1	3	5	3	5	6	4	6	3	6	5	6
2	2	5	2	6	2	4	2	3	2	5	2	4
3	4	6	4	1	3	1	5	1	4	1	3	1

규칙이 보인다..!

방 개수(N) 만큼 라운드가 진행되면 그 이후로는 같은 패턴이 반복된다.

이를 식으로 코드를 작성하면 되겠다.

 

라운드(M)가 방 개수(N)보다 작거나 같을 경우 그 값 만큼 라운드를 돌려서 구하면 되고,

라운드(M)가 방 개수(N)보다 큰 경우 N + (M % N) 으로 시뮬레이션을 돌려주면 된다.

 

이 정도로는 날 무너뜨릴 수 없다.

 

코드

#include<bits/stdc++.h>
using namespace std;
constexpr int LIMIT = 1002;
int N, M;
int score[LIMIT][3];

void move()
{
	int moveCnt;
	if (M <= N)	moveCnt = M;
	else		moveCnt = N + (M % N);

	for (int i = 0; i < moveCnt; i++)
	{
		int firstMoveIdx = 0;
		int moveIdx = 2;

		if (score[0][0] > score[0][1])
			firstMoveIdx = 1;

		for (int j = 1; j < N; j++)
		{
			if (score[j][0] > score[j][1])
			{
				score[j - 1][moveIdx] = score[j][0];
				moveIdx = 0;
			}
			else
			{
				score[j - 1][moveIdx] = score[j][1];
				moveIdx = 1;
			}
		}
		score[N-1][moveIdx] = score[0][firstMoveIdx];
		score[0][firstMoveIdx] = score[0][2];
	}
	
}
int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N >> M;
	for (int i = 0; i < N; i++)
		cin >> score[i][0] >> score[i][1];

	move();

	for (int i = 0; i < N; i++)
	{
		if(score[i][0] < score[i][1])
			cout << score[i][0] << " " << score[i][1] << "\n";
		else
			cout << score[i][1] << " " << score[i][0] << "\n";
	}
}