문제 링크
17406번: 배열 돌리기 4
크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의
www.acmicpc.net
접근 방법
처음에 문제를 해결하고 나서 왜맞틀을 시전했던 문제입니다. 문제를 잘 못 이해해서 생긴 문제인데 문제에서 배열의 회전 명령어를 순차적으로 실행하는 것이 아닌 주어진 명령어의 모든 조합을 다 실행하여 그 중 최소를 구하는 문제였습니다.
문제 풀이의 순서는 다음과 같습니다.
1. 가능한 명령의 조합을 구한다.
2. 한 조합에서 한 명령어를 실행한다.
3. 한 명령어를 실행한다.
4. 한 명령어에 s~1까지 순차적으로 배열을 회전 시킨다.
5. 한 조합의 명령어를 모두 실행시킨 후 배열의 값을 구한다.
6. 다음 조합도 위의 과정을 실행하며 최솟값을 갱신한다.
소스 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef struct info {
int r; int c; int s;
};
vector <vector<int>> map;
vector <info> inst;
int N, M, K;
void init() {
cin >> N >> M >> K;
for (int i = 0; i < N; i++) {
vector<int> v;
for (int j = 0; j < M; j++) {
int num; cin >> num;
v.push_back(num);
}
map.push_back(v);
}
for (int i = 0; i < K; i++) {
int r, c, s;
cin >> r >> c >> s;
inst.push_back({ r - 1, c - 1, s });
}
}
vector<vector<int>> sequence(vector<int> &seq, vector<vector<int>> &seqs, vector<bool> &visited) {
if (seq.size() == inst.size()) {
seqs.push_back(seq);
return seqs;
}
for (int i = 0; i < inst.size(); i++) {
if (!visited[i]) {
visited[i] = true;
seq.push_back(i);
sequence(seq, seqs, visited);
visited[i] = false;
seq.pop_back();
}
}
return seqs;
}
int findMin(vector<vector<int>> newmap) {
int minimum = 0xFFFFFFF;
for (int i = 0; i < N; i++) {
int sum = 0;
for (int j = 0; j < M; j++)
sum += newmap[i][j];
minimum = min(sum, minimum);
}
return minimum;
}
void rotate(int x, int y, int dist, vector<vector<int>> &ret) {
vector<vector<int>> tmp = ret;
for (int i = y - dist; i < y + dist; i++)
ret[x - dist][i + 1] = tmp[x - dist][i]; //높이 고정
for (int i = x - dist; i < x + dist; i++)
ret[i + 1][y + dist] = tmp[i][y + dist]; // 축 고정
for (int i = y + dist; i > y - dist; i--)
ret[x + dist][i - 1] = tmp[x + dist][i]; //높이 고정
for (int i = x + dist; i > x - dist; i--)
ret[i - 1][y - dist] = tmp[i][y - dist]; // 축 고정
}
int processing(vector<int> seq) { // 한 명령어 집합에 대한 것
vector<vector<int>> newmap = map;
for (int i = 0; i < seq.size(); i++) {
int r = inst[seq[i]].r;
int c = inst[seq[i]].c;
int s = inst[seq[i]].s;
for (int j = 1; j <= s; j++)
rotate(r, c, j, newmap);
}
return findMin(newmap);
}
int solve() {
vector <vector<int>> seqs;
vector <int> seq;
vector <bool> visited(6, false);
int minimum = 0xFFFFFFF;
seqs = sequence(seq, seqs, visited);
for (int i = 0; i < seqs.size();i++)
minimum = min(minimum, processing(seqs[i]));
return minimum;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
init();
cout << solve() << "\n";
}
개발 환경 : VS2017
질문, 지적 환영합니다!
'알고리즘 > 백준' 카테고리의 다른 글
| [C++] 백준 17472 다리만들기2 (0) | 2021.01.04 |
|---|---|
| [C++] 백준 17281 야구 (0) | 2021.01.04 |
| [C++] 백준 3190 뱀 (0) | 2021.01.03 |
| [C++] 백준 17136 색종이 붙이기 (0) | 2021.01.02 |
| [C++] 백준 9470 Strahler 순서 (0) | 2020.09.25 |
