글 읽기 - 2시간째 반례를 못찾고 있습니다. 도와주세요..

nablekim94 4년 전 0

제출 결과 : 틀렸습니다. (1퍼센트도 안오르고 바로 '틀렸습니다' 입니다.)

이 문제를 풀기 위해 생각한 아이디어는 다음과 같습니다.

연산자들의 순서, 즉 순열을 구한다.
1. 회전 연산 정보를 저장하기 위해 vector<CAL> calList를 이용했습니다.
2. 인덱스 값을 담는 order[]를 만들고 next_permutation을 통해 순열을 생성했습니다.
구한 순열대로 회전 연산을 수행한다.
1. order 배열의 값 순서를 회전 연산 사용 순서로 사용했습니다.
2. 시계방향으로의 회전은 사각형 기준 상,좌,하,우 순서로 큐에 배열 원소값을 임시로 저장한 후, 회전했을 때 자리할 위치에 다시 넣어줬습니다.
회전 연산 결과, 배열 A의 값(같은 행에 있는 원소들의 최소합) 구하기
1. 이중 for문써서 각 행에 있는 원소들의 합 구해서 vector에 넣기
2. vector를 오름차순 정렬해서 vector의 0번째 원소값을 최소값 후보로 정했습니다.
이전까지 구했던 배열 A의 최소값과 3번에서 구한 최소값 비교 후 갱신

혹시 제가 놓친 부분이나 잘못 생각한 부분이 있다면 말씀해주세요!!

감사합니다!!

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

struct CAL {
	int r, c, s;
};

int N, M, K;
int A[50][50];
vector<int> order;	// 순열 뽑기용
vector<CAL> calList;
int ans=987654321;

void calculate_A() {
	vector<int> sumList;

	for (int y = 0; y < N; y++) {
		int sum = 0;
		for (int x = 0; x < M; x++) {
			sum += A[y][x];
		}
		sumList.push_back(sum);
	}

	sort(sumList.begin(), sumList.end());

	ans = ans > sumList[0] ? sumList[0] : ans;
}

void rotate(int r, int c, int s) {
	queue<int> q;

	// q에 기존 배열의 원소값을 담기
	for (int i = c + s - 1; i >= c - s; i--)
		q.push(A[r - s][i]);

	for (int i = r-s+1; i <= r+s; i++)
		q.push(A[i][c-s]);

	for (int i = c - s + 1; i <= c + s; i++)
		q.push(A[r + s][i]);

	for (int i = r + s - 1; i >= r-s; i--)
		q.push(A[i][c+s]);
	
	// q에 담긴 원소를 이제 배열에 다시 넣어주기
	for (int i = c + s; i >= c - s; i--) {
		A[r - s][i] = q.front();
		q.pop();
	}

	for (int i = r - s + 1; i <= r + s; i++) {
		A[i][c - s] = q.front();
		q.pop();
	}

	for (int i = c - s + 1; i <= c + s; i++) {
		A[r + s][i] = q.front();
		q.pop();
	}

	for (int i = r + s - 1; i >= r - s+1; i--) {
		A[i][c + s] = q.front();
		q.pop();
	}
}

int main() {

	//freopen("Text.txt", "r", stdin);

	scanf(" %d %d %d", &N, &M, &K);
	
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			scanf(" %d", &A[y][x]);
		}
	}

	for (int i = 0, r, c, s; i < K; i++)
	{
		scanf(" %d %d %d", &r, &c, &s);
		calList.push_back({ r-1, c-1, s });	// 0번째 인덱스부터 사용할거라 -1 해줌
		order.push_back(i);
	}
	
	// 연산 순서 뽑기
	do {
		
		// 순서대로 배열돌리기 진행
		int calListSize = calList.size();
		
		// 각 회전 연산에 대하여 실시
		for (int i = 0; i < calListSize; i++) {
			int order_index = order[i];	// i번째로 사용할 회전 연산은 calList의 (order[i])번째 연산이다.

			// 한 회전 연산에서도 큰 테두리부터 작은 테두리까지 회전 실시
			for (int j = 0; j < calList[order_index].s; j++) {
				rotate(calList[order_index].r, calList[order_index].c, calList[order_index].s - j);
			}
		}

		calculate_A();
		

	} while (next_permutation(order.begin(), order.end()));

	printf("%d", ans);

	return 0;
}

ha_ram 4년 전 5

배열이 바뀐상태로 연산을 진행하는것 같습니다.=

연산 순서를 바꾼 후에 연산을 할 때

원래 배열에서 진행해야합니다.

nablekim94 4년 전 2

답변 감사합니다. 해결했어요~~

댓글을 작성하려면 로그인해야 합니다.