[백준 17406: 배열 돌리기 4] (C++)

삼성 A형 기출 문제

https://www.acmicpc.net/workbook/view/2771

ㄴ배열 돌리기 4

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

 

 

 

l 문제

 

1. 크기 NXM인 배열 ( 3 ≤ N, M ≤ 50 )

2. 배열 A의 값은 각 행에 있는 모든 수의 합 중 최소값

3. 회전 연산 세 정수 (r, c, s)로 이루어져있다. ( 1<= s ) 가장 왼쪽 위가 (r-s, c-s) 위치에서 가장 오른쪽 아래가 (r+s, c+s)인 정사각형을 시계 방향으로 한 칸씩 돌리는 연산이다. 총 K 번 연산이 가능하며 순서는 마음대로해도 되지만 모두 사용해야 한다. ( 1 <= K <= 6 )

 

 

l 입력

 

첫째 줄에 배열 A의 크기 N, M, 회전 연산의 개수 K가 주어진다.

둘째 줄부터 N개의 줄에 배열 A에 들어있는 수 A[i][j]가 주어지고, 다음 K개의 줄에 회전 연산의 정보 r, c, s가 주어진다.

 

 

l 출력

 

배열 A의 값의 최솟값을 출력한다.

 

 

l 풀이

 

next_permutaion로 순서를 정하고 회전 시킨다.

회전 함수 {   1. 가장 좌측 상단을 temp에 저장   2. 한쪽 방향으로 돌아가며 1칸 씩 차례로 밀어준다.   3. 마지막에 빈 자리에 temp를 넣는다. } 순열 함수 {   1. 돌리는 순서 정하기   2. 정해진 순서대로 회전   3. 최솟값 찾기 }

 

 

l  코드

 

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

struct rot_info
{
	int r, c, s;
} rot_data[7];
int N, M, K, ans;
vector<vector<int>> A;
vector<int> seq;

void rotation(int x, int y, int lv, vector<vector<int>> &board)
{
	x -= lv, y -= lv;
	int i, len = 2 * lv + 1;
	int center_data = board[x][y];

	for (i = 0; i < len - 1; ++i)
		board[x + i][y] = board[x + i + 1][y];
	x += len - 1;
	for (i = 0; i < len - 1; ++i)
		board[x][y + i] = board[x][y + i + 1];
	y += len - 1;
	for (i = 0; i < len - 1; ++i)
		board[x - i][y] = board[x - i - 1][y];
	x -= (len - 1);
	for (i = 0; i < len - 1; ++i)
		board[x][y - i] = board[x][y - i - 1];
	y -= (len - 1);
	board[x][y + 1] = center_data;
}

void simulation(vector<int> &rot_seq)
{
	// 2. 정해진 순서대로 회전
	vector<vector<int>> temp = A;
	for (auto &s : rot_seq)
		for (int i = 1; i <= rot_data[s].s; ++i)
			rotation(rot_data[s].r, rot_data[s].c, i, temp);

	// 3. 최솟값 찾기
	for (int i = 1; i <= N; ++i)
	{
		int sum = 0;
		for (int j = 1; j <= M; ++j)
			sum += temp[i][j];
		ans = min(ans, sum);
	}
}

int main()
{
	freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M >> K;
	ans = 987654321;
	A.resize(N + 1, vector<int>(M + 1));

	register int i, j;
	for (i = 1; i <= N; ++i)
		for (j = 1; j <= M; ++j)
			cin >> A[i][j];

	for (i = 1; i <= K; ++i)
	{
		cin >> rot_data[i].r >> rot_data[i].c >> rot_data[i].s;
		seq.push_back(i);
	}

	// 1. 돌리는 순서 정하기
	do{ 
		simulation(seq);
	} while (next_permutation(seq.begin(), seq.end()));

	cout << ans;
	return 0;
}

 

 

 

후기

 

2019년 8월 A형 시험 문제였습니다.

8월은 제가 처음으로 도전했던 A형 시험이었는데 1문제도 못 맞추고 불합격을 받았습니다.

시험장에서는 테스트케이스를 다맞추고 자신만만 했는데 예외 케이스에서 틀렸나봅니다 ㅠㅠ

틀린 이유라도 알 수 있으면 얼마나 좋을까요?

8월 시험은 쉬워서 A+을 퍼줬다는 소리를 들을 때마다 참 가슴이 아픕니다.

만약에 이때 땄으면 지금 B형 준비하고 있었을텐데 말이죠 

11월이 되어서 다시 준비하고 도전하고 있습니다. ㅋㅋㅋ

 

 

복원된 이 문제와는 약간의 차이가 있었고 훨씬 어려웠습니다.