[BOJ] 배열돌리기 2 (겉면부터 하나씩 돌려도 된다)

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

16927번: 배열 돌리기 2

 

처음에 뭐가 다르지? 했는데, R이 다르다

R이 1천 -> 10억이다.

 

시간이 오래 걸렸다. 몇시간 걸렸다. 왜 그랬는지 알아보자.

 

1. 뭔가 %로 나눠야한다는건 알았다. N*M으로 나눴다. 대체 왜 이런 생각을 했는지 모르겠다.

당연히 틀렸다.

 

2. 생각해보니까 맨 바깥 줄이 5*4에서 14번만에 제자리로 돌아오는것을 알았다.

식을 세워보니 (N-2) * 2 + (M-2) * 2 + 4 였다.

R을 저 위의 식으로 나눈 나머지로 바꿨다.

 

틀렸다. why?

5*4 를 예시로 들어보면, 맨 겉의 숫자는 14번만에 제자리를 찾아오지만, 그 안에 있는 사각형은 6번만에 제자리로 돌아온다.

 

따라서 14와 6의 최소공배수만큼 돌려야 아예 한바퀴 돌아서 제자리로 온다.

LCM(14,6) = 42를 했다.

 

42로 나눈 나머지로 하니까 잘 됐다.

 

3. 또 틀렸다. 왜일까?

300 300 10억 을 생각해보자.

LCM(1,2,3,4,5,6,7....)이 있다고 치면, LCM(1,2) , LCM( (1,2),3)

이런식으로 해야했다. 시간이 말도안되게 초과된다.

 

대체 왜 모든부분이 한번에 돌아와서 딱 맞아야한다고 생각했는지 모르겠다.

여기 생각에 갇혀서 몇시간은 꽁으로 날려먹은 것 같다.

 

4.

맨 마지막 생각.

5 4 일때 맨 겉에부분은 14번 돌면 끝나고, 안에는 6번 돌면 끝난다.

 

그럼 따로따로 돌려주면 된다고 생각했다.

즉 맨 겉면은 14로 나눈 나머지로, 내부는 6으로 나눈 나머지로.

그러니까 딱 되더라.

 

300 300 10억을 하더라도,

맨 겉에 원은 1196인데 ( 298 * 4 + 4 ) 이걸 10억으로 나눈 나머지로 하면 순식간에 줄어든다.

 

첫번째 사각형은 (N-2) * 2 + (M-2) * 2+ 4 이고

두번째 사각형은 (N-2 - 2) * 2 + (M-2 - 2) * 2+ 4 이고 // 위 아래 양 끝이 하나씩 줄기떄문에 -2씩..

 

(N+M-4 * i) * 2 + 4 를 하면 구할 수 있다.

N과 M이 5,4 이면, i = 1일때 14, i = 2일때 6이다.

 

a_i = -8i + 2(M+N) + 4 이다.

즉 공차가 -8 이고 a_1 = 2(M+N) - 4 이다.

 

14 6 -2 이런식으로 된다.

이제 각 테두리의 숫자의 개수를 알았으니, 각 테두리마다 R로 나눈 나머지 만큼만 돌리면, 가장 최소로 돌리면서 끝낼 수 있다.

 

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;

int board[303][303];
int N,M;
void func(int s, int R)
{
	int start;
	int t;
	for(int k = 0; k < R; k++){
		start = s;
		
			t = board[start][start];
			// col
			for(int i = start; i < M - start -1; i++)
			{
				board[start][i] = board[start][i+1];
			}
			// row
			for(int i = start; i < N - start -1; i++)
			{
				board[i][M-start-1] = board[i+1][M-start-1];
			}
			// col
			for(int i = M-start-1; i >= start+1; i--)
			{
				board[N-start-1][i] = board[N-start-1][i-1];
			}

			for(int i = N-start-1; i >= start+1 +1; i--)// 맨 마지막은 1개 빼야함
			{
				board[i][start] = board[i-1][start];
			}
			board[start+1][start] = t;
			
		
	}
	return;
}
int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int R;
	
	cin >> N >> M >> R;
	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < M; j++)
		{
			cin >> board[i][j];
		}
	}

	int t;
	int n = min(N,M) / 2;
	for(int i = 1; i <= n; i++)
	{
		t = -8 * i + (N+M) * 2 + 4;
		func(i-1, R % t);
	}

	for(int x = 0; x < N; x++)
	{
		for(int y = 0; y < M; y++)
		{
			cout << board[x][y] << " ";
		}
		cout << "\n";
	}
	// 방문하지않고 범위 벗어나지 않았으면 왼 또는 아래
	return 0;
    
}

 

지난번처럼 풀면

 

이렇게 굉장히 빠른 시간내에 할 수 있다.

 

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
int board[303][303];
int N,M;
void func(int s, int R)
{
	int dx[4] = {0,1,0,-1};
	int dy[4] = {1,0,-1,0};
	int start;
	int t;
	int mx = s, my = s;
	for(int k = 0; k < R; k++){
		t = board[s][s];
		for(int i = 0; i < 4; i++)
		{	
			while(true)
			{
				mx += dx[i];
				my += dy[i];
				if(mx < s || mx >= N-s || my < s || my >= M-s)
				{
					mx -= dx[i];
					my -= dy[i];
					break;
				}
				board[mx-dx[i]][my-dy[i]] = board[mx][my];
			}			
		}
		board[s+1][s] = t;
	}
	return;
}
int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int R;
	
	cin >> N >> M >> R;
	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < M; j++)
		{
			cin >> board[i][j];
		}
	}
	
	int t;
	int n = min(N,M) / 2;
	for(int i = 1; i <= n; i++)
	{
		t = -8 * i + (N+M) * 2 + 4;
		func(i-1, R % t);
	}

	for(int x = 0; x < N; x++)
	{
		for(int y = 0; y < M; y++)
		{
			cout << board[x][y] << " ";
		}
		cout << "\n";
	}
	return 0;   
}

 

이렇게 코드를 더 깔끔하게 할 수 있다.

근데 이건 외곽에 부딪히는 과정에서 추가적인 연산을 하므로 시간이 약간 더 걸린다.

물론 부딪히기 전까지 돌려줄 수 있다 .for문에 N과 M에 대한 추가적인 조건을 붙이면 된다.

중요한건, 내가 코테를 볼때 저 조건에서 등호나 숫자 1차이로 헛짓거리 하면 그게 더 헬이라.. 여기까지^^