[ Baekjoon ] 17406. 배열 돌리기 4

https://www.acmicpc.net/problem/17406

17406번: 배열 돌리기 4

풀이 방법

모든 연산 순서 조합을 구해서 각 순서에 대해 연산을 차례대로 수행한 후, 그 중 최소 배열 값을 반환한다.

 

우선 연산 순서 조합을 구하는 함수는 min_val()이다. K개의 연산에 대해 순서 조합을 구하면 Arr 클래스의 apply_ops() 메소드를 호출해 배열 값을 계산한다.

void min_val(int n, Arr& arr){
	static bool select[MAX_OPS] = {false, };
	static int order[MAX_OPS];
	if(n == K){
		ret = min(ret, arr.apply_ops(order));
	}
	else{
		for(int i=0; i<K; i++){
			if(!select[i]){
				select[i] = true;
				order[n] = i;
				min_val(n+1, arr);
				select[i] = false;
			}
		}
	}
}

 

Arr 클래스

Arr 클래스는 주어진 순서대로 연산을 수행하는 apply_ops() 메소드와 주어진 인덱스에 해당하는 연산을 한번 수행하는 rotate() 메소드가 존재한다.

class Arr{
public:
	Arr(int n, int m): N(n), M(m){
		for(int i=0; i<n; i++){
			for(int j=0; j<m; j++){
				cin >> A[i][j];
			}
		}
	};
	int apply_ops(int* order){};
private:
	int N, M;
	int A[MAX_SIZE][MAX_SIZE];

	void rotate(int op_idx){};
};

 

 

여러 번 호출되는 함수이기 때문에 copyA 배열에 원본 배열을 복사하여 연산을 적용한다. 그리고 주어진 순서대로 연산을 수행한 후, 배열의 값을 구한다.

Arr::apply_ops(int* order){
	int min_val = MAX_VAL, val;

	// copy origin array
	for(int i=0; i<N; i++){
		for(int j=0; j<M; j++){
			copyA[i][j] = A[i][j];
		}
	}

	// apply operations in given order
	for(int i=0; i<K; i++){
		rotate(order[i]);
	}

	// calculate value of the array
	for(int i=0; i<N; i++){
		val = 0;
		for(int j=0; j<M; j++){
			val += copyA[i][j];
		}
		min_val = min(min_val, val);
	}
    
	return min_val;
}

 

전체 코드는 여기서 확인할 수 있다.