[삼성 A형 기출문제] - 17406 배열 돌리기 4

실버2는 너무해 ㅠ.ㅠ

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

17406번: 배열 돌리기 4

 

입력

• map에 배열을 입력받았다.
• 회전 연산의 정보는 따로 벡터에 담았다.
• 벡터에 구조체로 넣어서 하려고 했는데, 3개 이상의 값을 구조체에 넣으면 크기 순으로 따로 정렬을 해야되고 귀찮아서 vector<pair<pair<int, int>,int>>v; 로 때려박았다

구현

구현은 3가지를 중점적으로 생각했다.

1. 연산에 맞게 배열을 회전시키기 --> rotate 함수 사용
2. 연산의 순서를 정하기 --> next_permutation 사용
3. 각 행별로 더하기 --> calc 함수 사용

우선, `rotate` 함수의 구현은 다음과 같다.

• 배열을 움직여야 하므로 backup 배열에 memcpy 해두었다.
• 움직이는 것은 정사각형으로 움직이므로 좌상단, 우상단의 좌표를 저장해두고 그에 맞게 배열을 이동했다.
• 예를들어 5x5 정사각형이 이동해야하면, 가장 바깥쪽의 정사각형 라인이 움직이고 그 안쪽에 있는 3x3 정사각형도 움직여야 한다.
• while loop을 돌며 좌상단과 우하단의 좌표가 같아지면 1x1 정사각형이다.
• 즉, 가장 안쪽에 있는 정사각형에 도달한 것이므로 이동이 끝났음을 의미한다. break로 탈출한다.

연산의 순서를 정하는 것은 next_permutation을 사용했다. next_permutation은 조사하는 배열의 크기가 20정도만 되어도 시간초과의 위험이 있지만 K가 최대 6이므로 시간초과의 위험은 없다.

• 벡터에 입력받은 회전 연산에 대해 순열을 구했다. 이 값을 rotate 함수에 인자값으로 넘겨주어 rotate 함수에서 좌상단, 우하단 좌표 값을 계산할 수 있다.
• next_permutation 은 정렬된 리스트에만 적용할 수 있으므로 벡터를 정렬해주는것이 중요하다. 어차피 순열만 구하면 되기 때문에 크기순으로 정렬이 되든, 역순으로 정렬이 되든 큰 상관이 없다.

마지막으로 각 행별로 더하여 최소값을 찾는 것은 크게 어렵지 않다.

• 연산의 순서에 맞게 rotate 함수가 끝나고 최종적으로 이동이 완료된 배열을 각 행별로 더해가며 최소값을 구하고 그 값을 return 해주면 된다

소스코드

 

	#include<iostream>
	#include<vector>
	#include<algorithm>
	#include<string.h>
	#define MAX 51
	using namespace std;
	int n, m, k;
	int r, c, s;
	int map[MAX][MAX];
	int backup[MAX][MAX];
	int tmp_backup[MAX][MAX];
	vector<pair<pair<int, int>,int>>v;
	int calc() { // 행의 합들 중 최솟값
	int res = 987654321;
	for (int i = 1; i <= n; i++) {
	int cur = 0;
	for (int j = 1; j <= m; j++) {
	cur += backup[i][j];
	}
	res = min(cur, res);
	}
	return res;
	}
	void rotate(int R,int C,int S) {
	memcpy(tmp_backup, backup, sizeof(tmp_backup));
	int left_y = R - S; int left_x = C - S;
	int right_y = R + S; int right_x = C + S;
	while (true) {
	// 오른쪽으로 진행
	for (int j = left_x; j < right_x; j++) {
	backup[left_y][j + 1] = tmp_backup[left_y][j];
	}
	// 아래쪽으로 진행
	for (int i = left_y; i < right_y; i++) {
	backup[i + 1][right_x] = tmp_backup[i][right_x];
	}
	// 왼쪽으로 진행
	for (int j = right_x; j > left_x; j--) {
	backup[right_y][j - 1] = tmp_backup[right_y][j];
	}
	// 위쪽으로 진행
	for (int i = right_y; i > left_y; i--) {
	backup[i - 1][left_x] = tmp_backup[i][left_x];
	}
	// 배열의 안쪽도 진헹
	left_y++; left_x++; right_y--; right_x--;
	// 정사각형이므로, 가운데 점에 도착하면 끝
	if ((left_y == right_y) && (left_x == right_x)) {
	break;
	}
	}
	}
	int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	freopen("input.txt", "r", stdin);
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= m; j++) {
	cin >> map[i][j];
	}
	}
	for (int i = 0; i < k; i++) {
	cin >> r >> c >> s;
	v.push_back({{r,c},s});
	}
	sort(v.begin(), v.end()); // 이게 없어서 틀렸었음
	int result = 987654321;
	do
	{
	memcpy(backup, map, sizeof(backup));
	for (int i = 0; i <v.size(); i++) {
	rotate(v[i].first.first, v[i].first.second, v[i].second);
	}
	result = min(calc(), result);
	} while (next_permutation(v.begin(), v.end()));
	cout << result;
	}

view raw 17406_배열 돌리기4.cpp hosted with ❤ by GitHub