백준17406 : 배열 돌리기4
배열 돌리기 4
| 1 초 | 512 MB | 11699 | 4938 | 3370 | 39.122% |
문제
크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다.
1 2 3
2 1 1
4 5 6
배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 방향으로 한 칸씩 돌린다는 의미이다. 배열의 칸 (r, c)는 r행 c열을 의미한다.
예를 들어, 배열 A의 크기가 6×6이고, 회전 연산이 (3, 4, 2)인 경우에는 아래 그림과 같이 회전하게 된다.
A[1][1] A[1][2] → A[1][3] → A[1][4] → A[1][5] → A[1][6]
↑ ↓
A[2][1] A[2][2] A[2][3] → A[2][4] → A[2][5] A[2][6]
↑ ↑ ↓ ↓
A[3][1] A[3][2] A[3][3] A[3][4] A[3][5] A[3][6]
↑ ↑ ↓ ↓
A[4][1] A[4][2] A[4][3] ← A[4][4] ← A[4][5] A[4][6]
↑ ↓
A[5][1] A[5][2] ← A[5][3] ← A[5][4] ← A[5][5] ← A[5][6]
A[6][1] A[6][2] A[6][3] A[6][4] A[6][5] A[6][6]
회전 연산이 두 개 이상이면, 연산을 수행한 순서에 따라 최종 배열이 다르다.
다음은 배열 A의 크기가 5×6이고, 회전 연산이 (3, 4, 2), (4, 2, 1)인 경우의 예시이다.
| 배열 A | (3, 4, 2) 연산 수행 후 | (4, 2, 1) 연산 수행 후 |
| 배열 A | (4, 2, 1) 연산 수행 후 | (3, 4, 2) 연산 수행 후 |
배열 A에 (3, 4, 2), (4, 2, 1) 순서로 연산을 수행하면 배열 A의 값은 12, (4, 2, 1), (3, 4, 2) 순서로 연산을 수행하면 15 이다.
배열 A와 사용 가능한 회전 연산이 주어졌을 때, 배열 A의 값의 최솟값을 구해보자. 회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 된다.
입력
첫째 줄에 배열 A의 크기 N, M, 회전 연산의 개수 K가 주어진다.
둘째 줄부터 N개의 줄에 배열 A에 들어있는 수 A[i][j]가 주어지고, 다음 K개의 줄에 회전 연산의 정보 r, c, s가 주어진다.
출력
배열 A의 값의 최솟값을 출력한다.
배열돌리기
배열을 돌리고,dfs로 뭐부터 돌려야 최소값을 받는지 확인하면 된다.
그리고 순열을 써서 돌려야하는데, 순열 사용하는 방법을 잘 모르겠다. next_permutation으로 돌려야하는데,
저번에 한번 써보고 안쓴지 오래되서 다시 공부좀 해보고 문제를 풀어서 올리겠다.
현재까지의 코드이다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int arr[101][101];
bool visited[6];
int order[6];
int N, M, K;
int answer = 987654321;
vector<pair<int, pair<int, int>>>v;
void roll_square(int r,int c, int s) {
int copy[101][101] = { 0 , };
for (int i = r - s; i <= r + s; i++)
for (int j = c - s; j <= c + s; j++)
copy[i][j] = arr[i][j];
int k = s;
for (int i = 0; i < k; i++) {
for (int x = c - s; x < c + s; x++)
arr[r - s][x + 1] = copy[r - s][x];
for (int y = r - s; y < r + s; y++)
arr[y + 1][c + s] = copy[y][c + s];
for (int x = c + s; x > c - s; x--)
arr[r + s][x - 1] = copy[r + s][x];
for (int y = r + s; y > r - s; y--)
arr[y - 1][c - s] = copy[y][c - s];
s--;
}
}
void print() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
cout << arr[i][j];
}cout << endl;
}
}
int main() {
cin >> N >> M >> K;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
cin >> arr[i][j];
for (int i = 0; i < K; i++)
cin >> v[i].first >> v[i].second.first >> v[i].second.second;
do {
} while (next_permutation(v.begin(), v.end()));
print();
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int arr[51][51];
int temp[51][51];
bool visited[7];
int N, M, K;
int answer = 987654321;
vector < pair< pair<int,int>, int>> v;
vector<int> permutation;
void print() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
cout << arr[i][j];
}cout << endl;
}
}
void roll_square(int r,int c, int s) {
int copy[51][51] = { 0 , };
for (int i = r - s; i <= r + s; i++)
for (int j = c - s; j <= c + s; j++)
copy[i][j] = arr[i][j];
int k = s;
for (int i = 0; i < k; i++) {
for (int x = c - s; x < c + s; x++)
arr[r - s][x + 1] = copy[r - s][x];
for (int y = r - s; y < r + s; y++)
arr[y + 1][c + s] = copy[y][c + s];
for (int x = c + s; x > c - s; x--)
arr[r + s][x - 1] = copy[r + s][x];
for (int y = r + s; y > r - s; y--)
arr[y - 1][c - s] = copy[y][c - s];
s--;
}
}
void dfs(int depth) {
if (depth == K) {
for (int a = 1; a <= N; a++)
for (int b = 1; b <= M; b++)
arr[a][b] = temp[a][b];//초기화
for (int i = 0; i < depth; i++) {
int s = permutation[i]-1;
roll_square(v[s].first.first, v[s].first.second, v[s].second);
}
for (int i = 1; i <= N; i++) {
int sum = 0;
for (int j = 1; j <= M; j++) {
sum += arr[i][j];
}
answer = min(sum, answer);
}
return;
}
for (int i = 1; i <= K; i++) {
if (visited[i] == false) {
visited[i] = true;
permutation.push_back(i);
dfs(depth+1);
permutation.pop_back();
visited[i] = false;
}
}
}
int main() {
cin >> N >> M >> K;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++) {
cin >> arr[i][j];
temp[i][j] = arr[i][j];
}
int a,b,c;
for (int i = 0; i < K; i++) {
cin >> a >> b >> c;
v.push_back({ {a,b},c });
}
dfs(0);
cout << answer;
return 0;
}
깔끔~_~하게 풀었다 기모찌
dfs로 순열을 짜줘도 되지만, next_permutation이라는 함수를 이용해도 된다. 근데 왠지 함수 익히는게 더 어렵게 느껴져서 그냥 dfs로 짜줬다.