17406번: 배열 돌리기 4
크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의
www.acmicpc.net
1. 풀이 방법
- 경우의 수는 명령의 순서에 따라 결과가 달라지므로 순열로 구했습니다.
- 회전을 구현해야 하는데, 바깥쪽 부터 한 겹씩 회전을 시키는 순으로 했고
=
맨 안쪽에 남은 하나는 오른쪽으로 가려고 하는데 이미 방문한 곳이면 break 하게끔 하였습니다.
-코드가 많이 길어졌네요...ㅠ
2.주의할 점.
- 코드가 길어지다보니 처음 짠 부분에서 이곳 저곳에서 문제가 발생...
디버깅을 한참했습니다...
-디버깅을 아예 안하기는 쉽지 않겠지만 처음 짤 때 그래도 좀 세심하게 해야겠네요...
-그리고 (r-s,r+s) 입력이 이런식 이기때문에 행과 열의 수는 모두 홀수 입니다.
(처음에 짝수 개도 되는 경우의 수도 생각하고 짰었는데...풀다보니 발견...)
- 조건에 따른 문제를 정확하게 파악해야겠습니다...
3. 나의코드
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N, M;
int K,r,s;
int doublearr[51][51]; //본 2차원 배멸 (변화 x)
int caculdoublearr[51][51]; //case별 결과값을 뽑아내기 위한 배열
int copydoublearr[51][51]; //이동을 위해 값을 복사해놓을 임시배열
bool check[51][51];
bool selected[7];
vector<int> resultmin;
struct rcs {
int r,c,s;
};
vector<rcs> command; //입력받은명령
vector<rcs> casecommand; // 각 경우의수 (시뮬레이션 돌릴)
void input() { // 입력받는 함수
cin >> N >> M >> K;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
cin >> doublearr[i][j];
}
}
rcs tmp;
for (int i = 0; i < K; i++) {
cin >> tmp.r >> tmp.c >> tmp.s;
command.push_back(tmp);
}
}
void copyarr() { // 원본배열은 그대로 두고 복사해서 사용 (각 테스트케이스마다 써야하므로)
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
copydoublearr[i][j] = doublearr[i][j];
caculdoublearr[i][j] = doublearr[i][j];
}
}
}
void initcheck() { // 방문배열 초기화
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
check[i][j] = false;
}
}
}
void copycal() { //한번회전한 배열을 계산을 위한 배열에 복사
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
copydoublearr[i][j] = caculdoublearr[i][j];
}
}
}
void turnarr(int r, int c, int s) { //회전을 구현
int x = r - s;
int y = c - s;
int tmpcount = 0;
int totalcount = 8 * s; //연산해야하는 횟수 한 바퀴에
char dir = 'R';
initcheck();
while (1) {
if (totalcount == tmpcount) { //바깥한바퀴 -> 안쪽 바퀴로 들어감
x += 1; y += 1; s -= 1; totalcount = 8 * s;
tmpcount = 0;
}
if (dir == 'R') {
if (check[x][y+1] == true) { copycal(); break;
}
caculdoublearr[x][y + 1] = copydoublearr[x][y];
tmpcount++;
check[x][y] = true;
y += 1;
if (y == c + s) { dir = 'D'; }
}
else if (dir == 'D') {
caculdoublearr[x + 1][y] = copydoublearr[x][y];
tmpcount++;
check[x][y] = true;
x += 1;
if (x == r + s) { dir = 'L'; }
}
else if (dir == 'L') {
caculdoublearr[x][y - 1] = copydoublearr[x][y];
tmpcount++;
check[x][y] = true;
y -= 1;
if (y == c - s) { dir = 'U'; }
}
else {
caculdoublearr[x - 1][y] = copydoublearr[x][y];
tmpcount++;
check[x][y] = true;
x -= 1;
if (x == r - s) { dir = 'R'; }
}
}
}
int getmin() { //배열의 최소값을 뽑아내는 함수
int mini = 5001;
for (int i = 1; i <= N; i++) {
int tmpsum = 0;
for (int j = 1; j <= M; j++) {
tmpsum += caculdoublearr[i][j];
}
if (tmpsum < mini) { mini = tmpsum; }
}
return mini;
}
void relocating() { //명령을 수행 (회전명령)
copyarr();
for (int i = 0; i < K; i++) {
turnarr(casecommand[i].r, casecommand[i].c, casecommand[i].s);
}
resultmin.push_back(getmin());
}
void simulation(int n) { //순열 경우의 수 생성
if (n == K) {
relocating();
return;
}
for (int i = 0; i < command.size(); i++) {
if (selected[i] == true) continue;
selected[i] = true;
casecommand.push_back(command[i]);
simulation(n+1);
casecommand.pop_back();
selected[i] = false;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
input();
simulation(0);
sort(resultmin.begin(), resultmin.end());
cout << resultmin[0];
return 0;
}'알고리즘 문제풀이 > 구현' 카테고리의 다른 글
| 백준 2033 C++ (0) | 2020.11.25 |
|---|---|
| 백준 14890 [C++] (0) | 2020.10.21 |
| 백준 15686 [C++] (0) | 2020.10.17 |
| 백준 3190 [C++] (0) | 2020.10.17 |
| 백준 18406 [C++] (0) | 2020.10.16 |
