[시뮬레이션] BOJ 16927 배열 돌리기 2 - 오답노트

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

16927번: 배열 돌리기 2

-문제 파악

배열돌리기1 의 시간복잡도 버전

 

- 나의 접근

배열을 돌렸을 때 첫번째 배열로 돌아오는 수를 찾아서 문제에서 주어지는 돌리는 횟수를 나눈 나머지 만큼만 돌릴려고 했지만, 돌아오는 수가 너무 큰건지 계속 런타임 오류가 발생했다.

 

- 정답

그래서 가장 바깥 배열부터 차례대로 위의 접근 방식을 적용하기로 했다.

(나의 접근 : 주어진 배열 전부가 처음으로 돌아오는 횟수로 나머지를 찾는 방법

 정      답  : 주어진 배열을 바깥쪽부터 처음으로 돌아오는 횟수로 나머지를 찾고 안쪽으로 넘어가는 방법   )

각 구역의 배열을 돌려서 처음으로 돌아오는 횟수는 2*(n-(2*k)) + 2*(m-(2*k)) 이다. (n,m은 문제에서 주어진 가로,세로 길이이고 k는 0부터 시작하여 안쪽의 배열을 돌릴때 마다 1씩 증가한다. 

 

#include "bits/stdc++.h"

using namespace std;

int n, m, t;
int arr[305][305];
int arr_tmp[305][305];

void T2B(int x, int y, int dn, int dm)
{
	for (int i = x; i < dn - 1; i++)
	{
		arr_tmp[i + 1][y] = arr[i][y];
	}
}

void L2R(int x, int y, int dn, int dm)
{
	for (int i = y; i < dm - 1; i++)
	{
		arr_tmp[x][i + 1] = arr[x][i];
	}
}

void B2T(int x, int y, int dn, int dm)
{
	for (int i = dn - 1; i > x; i--)
	{
		arr_tmp[i - 1][y] = arr[i][y];
	}
}

void R2L(int x, int y, int dn, int dm)
{
	for (int i = dm - 1; i > y; i--)
	{
		arr_tmp[x][i - 1] = arr[x][i];
	}
}

void arrcpy(int dx, int dy, int dn, int dm)
{
	int ndx = n - dx - 1;
	int ndy = m - dy - 1;

	for (int i = dx; i < dn; i++)
	{
		arr[i][dy] = arr_tmp[i][dy];
	}

	for (int i = dy; i < dm; i++)
	{
		arr[ndx][i] = arr_tmp[ndx][i];
	}

	for (int i = dn - 1; i >= dx; i--)
	{
		arr[i][ndy] = arr_tmp[i][ndy];
	}

	for (int i = dm - 1; i >= dy; i--)
	{
		arr[dx][i] = arr_tmp[dx][i];
	}

}

int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> n >> m >> t;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> arr[i][j];
		}
	}

	

	//while (t--)
	{
		int dn = n;
		int dm = m;
		int dx = 0;
		int dy = 0;
		int k = 0;
		while (dx < dn && dy < dm )
		{
			int nt = 2 * (n - (2 * k)) + 2 * (m - (2 * k)) - 4;
			int nR = t % nt;
			while (nR--)
			{
				T2B(dx, dy, dn, dm);
				L2R(n - dx - 1, dy, dn, dm);
				B2T(dx, m - dy - 1, dn, dm);
				R2L(dx, dy, dn, dm);

				arrcpy(dx, dy, dn, dm);
				//memcpy(arr, arr_tmp, sizeof(int) * 305 * 305);
				
			}
			k++;
			dx++;
			dy++;
			dn--;
			dm--;
		}

		

	}


	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cout << arr[i][j] << " ";
		}
		cout << "\n";
	}

}