Problem 문제풀이
재귀함수를 사용했으면 꼭 return하는 습관을 들이자. 싫으면 void쓰든가!
return안 해서 run time error를 받을 수 있다는 건 또 처음 알았다. 각설하고,
전략
-
조합이 나오면 N과 M을 떠올리자. K개의 rotate명령을 나열하는 모든 경우를 찾자.
-
나열을 완료하였으면 그 순서대로 명령을 실행시킨다.
-
rotate함수를 구현한다.
-
명령을 다 수행하였으면 배열의 행의 누적합의 최솟값을 갱신한다.
먼저 rotate명령을 저장할 struct와 vector를 만들자.
struct RotateInfo {
int row;
int col;
int len;
RotateInfo(int _row, int _col, int _len) :row(_row), col(_col), len(_len) {}
};
vector<RotateInfo> ri;
이 후 rotate시킬 순서를 정하자.
void comb(int idx)
{
if (idx == K)
{
int** _A = new int* [N];
for (int i = 0; i < N; i++)
{
_A[i] = new int[M];
for (int j = 0; j < M; j++)
{
_A[i][j] = arr[i][j];
}
}
solve(_A, 0);
return;
}
for (int i = 0; i < K; i++)
{
if (used[i] == 0)
{
order[idx] = i;
used[i] = 1;
comb(idx + 1);
used[i] = 0;
}
}
}
idx==K 라는 것은 모든 순서를 다 정했다는 뜻이다. 이제 simulation을 구현하자.
void solve(int** _A, int idx)
{
if (idx == K)
{
int tmp = cnt(_A);
if (answer == -1 || answer > tmp)
{
answer = tmp;
}
return;
}
int** A = new int* [N];
for (int i = 0; i < N; i++)
{
A[i] = new int[M];
for (int j = 0; j < M; j++)
{
A[i][j] = _A[i][j];
}
}
rotate(A, _A, idx);
solve(A, idx + 1);
}
마지막으로 rotate를 구현하자. 여기서 실수가 많이 나온다.
꼭지점에서 값의 갱신에 유의하자!
void rotate(int** _A, int **A, int idx)
{
int row = ri[order[idx]].row;
int col = ri[order[idx]].col;
int len = ri[order[idx]].len;
for (int l = 1; l <= len; l++)
{
for (int i = row - l; i <= row + l; i++)
{
if (i == row - l || i == row + l)
{
for (int j = col - l + 1; j < col + l; j++)
{
if (i == row - l)
{
_A[i][j] = A[i][j - 1];
}
else
{
_A[i][j] = A[i][j + 1];
}
}
if (i == row - l)
{
_A[i][col - l] = A[i + 1][col - l];
_A[i][col + l] = A[i][col + l - 1];
}
else
{
_A[i][col - l] = A[i][col - l + 1];
_A[i][col + l] = A[i - 1][col + l];
}
}
else
{
_A[i][col - l] = A[i + 1][col - l];
_A[i][col + l] = A[i - 1][col + l];
}
}
}
}
원래 동적 배열을 선언할 경우 delete해줘야하는데 귀찮아서 생략했다..
혹시 문제가 될 수도 있으니 delete하는 방법은 알아두자!
for(int i=0;i<N;i++)
{
delete[] A[i];
}
delete[] A;
new 연산자의 역순으로 기억하면 편할 것이다.
끝으로 전체 코드를 남기며 마무리한다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct RotateInfo {
int row;
int col;
int len;
RotateInfo(int _row, int _col, int _len) :row(_row), col(_col), len(_len) {}
};
int N, M, K, r, c, s, answer;
int used[7];
int arr[51][51];
int order[7];
vector<RotateInfo> ri;
void comb(int idx);
void solve(int** _A, int idx);
int cnt(int** _A);
void rotate(int** _A, int** A, int idx);
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M >> K;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cin >> arr[i][j];
}
}
for (int i = 0; i < K; i++)
{
cin >> r >> c >> s;
ri.push_back(RotateInfo(r-1, c-1, s));
}
answer = -1;
comb(0);
cout << answer;
return 0;
}
void comb(int idx)
{
if (idx == K)
{
int** _A = new int* [N];
for (int i = 0; i < N; i++)
{
_A[i] = new int[M];
for (int j = 0; j < M; j++)
{
_A[i][j] = arr[i][j];
}
}
solve(_A, 0);
return;
}
for (int i = 0; i < K; i++)
{
if (used[i] == 0)
{
order[idx] = i;
used[i] = 1;
comb(idx + 1);
used[i] = 0;
}
}
}
void solve(int** _A, int idx)
{
if (idx == K)
{
int tmp = cnt(_A);
if (answer == -1 || answer > tmp)
{
answer = tmp;
}
return;
}
int** A = new int* [N];
for (int i = 0; i < N; i++)
{
A[i] = new int[M];
for (int j = 0; j < M; j++)
{
A[i][j] = _A[i][j];
}
}
rotate(A, _A, idx);
solve(A, idx + 1);
}
void rotate(int** _A, int **A, int idx)
{
int row = ri[order[idx]].row;
int col = ri[order[idx]].col;
int len = ri[order[idx]].len;
for (int l = 1; l <= len; l++)
{
for (int i = row - l; i <= row + l; i++)
{
if (i == row - l || i == row + l)
{
for (int j = col - l + 1; j < col + l; j++)
{
if (i == row - l)
{
_A[i][j] = A[i][j - 1];
}
else
{
_A[i][j] = A[i][j + 1];
}
}
if (i == row - l)
{
_A[i][col - l] = A[i + 1][col - l];
_A[i][col + l] = A[i][col + l - 1];
}
else
{
_A[i][col - l] = A[i][col - l + 1];
_A[i][col + l] = A[i - 1][col + l];
}
}
else
{
_A[i][col - l] = A[i + 1][col - l];
_A[i][col + l] = A[i - 1][col + l];
}
}
}
}
int cnt(int** _A)
{
int ret = -1;
for (int i = 0; i < N; i++)
{
int sum = 0;
for (int j = 0; j < M; j++)
{
sum += _A[i][j];
}
if (ret == -1 || ret > sum)
{
ret = sum;
}
}
return ret;
}