글 읽기 - 어느 부분이 잘못되었는지 알 수 있을까요?

swang95 4년 전 0

예제는 잘 돌아가는데 틀렸다고 나옵니다.

혹시나 회전이 잘못 구현됐나 싶어서 회전 후의 배열 값을 직접 출력해봤는데 예제의 배열값과 같은 걸 보니 잘 돌아가는 것 같습니다.

순서 또한 0 1 2 3 4 5 부터 5 4 3 2 1 0 까지 모든 경우를 탐색합니다. (6번 회전하는 경우)

분명 논리적인 오류가 있을건데 어디서 틀린건지 안보입니다.

찾아주시면 감사하겠습니다.

######

제가 생각한 풀이법은 다음과 같습니다.

회전할 수 있는 중심 점이 3개면

1, 2, 3

1, 3, 2

2, 1, 3

2, 3, 1

3, 1, 2

3, 2, 1

이런식으로 모든 순서의 경우의 수를 만든 다음에 해당 순서에 맞게 회전시킨 뒤

배열의 row값의 합 중에 최소를 찾는 것이라고 이해했습니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class node {
public:
	int y;
	int x;
	int l;

	node(int a, int b, int c) {
		y = a, x = b, l = c;
	}
};

int N, M, K;
int cmap[50][50];
vector<node> vec;
vector<int> permu;

int get_min(int map[50][50]) {
	int ret = 50 * 100 + 1;
	for (int i = 0; i < N; i++) {
		int local = 0;
		for (int j = 0; j < M; j++) {
			local += map[i][j];
		}
		ret = min(ret, local);
	}
	return ret;
}

int solve() {
	int map[50][50];
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			map[i][j] = cmap[i][j];
		}
	}
	
	for (int k = 0; k < permu.size(); k++) {
		int index = permu[k];
		int Y = vec[index].y, X = vec[index].x, L = vec[index].l;
		for (int l = 1; l <= L; l++) {
			int temp = map[Y - l][X - l];
			for (int x = X - l; x < X + l; x++) {
				int temp2 = map[Y - l][x + 1];
				map[Y - l][x + 1] = temp;
				temp = temp2;
			}

			for (int y = Y - l; y < Y + l; y++) {
				int temp2 = map[y + 1][X + l];
				map[y + 1][X + l] = temp;
				temp = temp2;
			}

			for (int x = X + l; x > X - l; x--) {
				int temp2 = map[Y + l][x - 1];
				map[Y + l][x - 1] = temp;
				temp = temp2;
			}

			for (int y = Y + l; y > Y - l; y--) {
				int temp2 = map[y - 1][X - l];
				map[y - 1][X - l] = temp;
				temp = temp2;
			}
		}
	}
	int ret = get_min(map);
	
	return ret;
}

int main() {
	cin >> N >> M >> K;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> cmap[i][j];
		}
	}
	
	
	for (int i = 0; i < K; i++) {
		int y, x, k;
		cin >> y >> x >> k;
		vec.push_back(node(y - 1, x - 1, k));
		permu.push_back(i); // permu vector에 0, 1, 2, 3, ..., K-1 까지 수를 저장
	}
	int ans = get_min(cmap);
    
    // 순열을 사용해서 회전 순서를 정한다.
	do {
		ans = min(ans, solve());
	} while (next_permutation(permu.begin(), permu.end()));
	cout << ans;
}

gmasi112 4년 전 1

94번 줄의 ans에 get_min을 호출하시면 안됩니다.

그 경우가 최솟값인것은 문제에서 원하는 정답이 아닙니다.

그 부분만 바꾸니 통과되네요~

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

문제

문제

출처

ICPC

어느 부분이 잘못되었는지 알 수 있을까요?

swang95 4년 전 0

gmasi112 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말