[BOJ] 16926. 배열돌리기 1

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

16926번: 배열 돌리기 1

배운점 :

규칙적으로 돌리면 코드가 더 깔끔해진다. ^^ (

​

죄송합니다.. 설명하려고 그림 그렸는데 다 푼 문제에 똥을 뿌려버렸네요

​

그.. 삽입정렬 아시죠?

2,3,4,5 에서 배열을 추가하지 않고 옮기려면 어떻게 했나요?

​

X 2 3 4 5

맨 뒤에 1칸을 더 할당해서 맨 오른쪽부터 왼쪽으로 이동하면서 왼쪽의 원소를 오른쪽으로 넣습니다(a[n+1] = a[n]) . 이렇게 하면 in-place로 옮기는게 가능합니

다.

​

마찬가지로..

이것도

(x,x)를 미리 빼놓습니다. ex) 0,0 , 1,1

그다음 오른쪽 부터 끌어당겨서,,

 

제발 제 진심이 닿기를 바랍니다.

한 칸을 더 추가할수는 없으니, 하나 빼놓습니다..

죄송해요 설명을 못하겠어요.

암튼 제 전략은

한칸을 뺀다음에 퍼즐 옮기듯이 쭈르륵 옮기고, 맨 마지막에 빼놓은걸 다시 넣는 전략입니다.

 

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int board[303][303];
int main(void)
{
    ios::sync_with_stdio(0);
	cin.tie(0);
	int N,M,R;
	cin >> N >> M >> R;
	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < M; j++)
		{
			cin >> board[i][j];
		}
	}

	// row col row col + + - -
	int start;
	int t;
	for(int k = 0; k < R; k++){
		start = 0;
		while(start < min(N,M)/2)
		{
			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;
			start++;
		}
	}

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

이리저리 N과 M을 대입해가며 규칙성을 찾는 방법이 있고..

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int board[303][303];
int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int N,M,R;
	cin >> N >> M >> R;
	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < M; j++)
		{
			cin >> board[i][j];
		}
	}
    // 우, 하, 좌, 상
    int dx[4] = {0,1,0,-1};
    int dy[4] = {1,0,-1,0};
	// row col row col + + - -
	int start;
	int t;
    int mx,my;

	for(int k = 0; k < R; k++){
		start = 0;
		while(start < min(N,M)/2)
		{
			t = board[start][start];
            mx = start;
            my = start;
            for(int i = 0; i < 4; i++)
            {    
                while(true)
                {
                    mx += dx[i];
                    my += dy[i];
                    if( mx < start || mx >= N-start || my < start || my >= M-start) 
                    {
                        mx -= dx[i];
                        my -= dy[i];
                        break;
                    }
                    board[mx-dx[i]][my-dy[i]] = board[mx][my];
                }
            }	
			board[start+1][start] = t;
			start++;
		}
	}
	for(int x = 0; x < N; x++)
	{
		for(int y = 0; y < M; y++)
		{
			cout << board[x][y] << " ";
		}
		cout << "\n";
	}
	return 0;
    
}

부딪히면 다시 되돌아가! 라고 그냥 뇌를 빼는 풀이가 있습니다.

​

참고로 1이 2보다 2배정도 빠릅니다. 쩝.. 암튼.. 여기까지

152ms -> 방임형

72ms -> 꼼꼼형

​

열정.. 열정 열정...