[6318번] Box of Bricks

영어로 된 문제를 처음 풀어본다...! 영어로 쓰여져 있으면 괜히 더 어려워보인다. 사실은 복잡하지 않은 문제였다!

어쨋든 시작,

문제를 요약하자면 다음과 같이 벽돌은 몇개의 스택으로 나누어 쌓는다고 가정한다. 

스택의 길이를 일정하게 유지하지 않고 쌓은 뒤, 최소한의 움직임으로 전체 스택의 길이를 맞추어주는 문제이다. 

 

 

이때 개인적으로 생각했을 때 잊어버리지 말아야할 조건은

1. 위와 같은 형태를 한 세트라고 두었을 때, 입력은 여러 세트가 가능하다.
2. 0이 입력되었을 때 입력이 끝났음을 알 수 있다. (0에 대해선 계산을 돌지 않는다.)
3. 벽돌의 전체 수는 스택의 개수로 나누어 떨어진다. 즉, 남는 벽돌이 없다는 뜻이다.

 

다음은 코드이다.

먼저 각 세트의 최소 이동 벽돌 수를 구해주는 함수를 작성하였다.

int findMin(int nStack, int nBrick[]) {
	int sumBricks = 0, BricksByStack = 0, minCount = 0;
	for (int i = 0; i < nStack; i++) {
		sumBricks += nBrick[i];
	}
	if (nStack != 0) {
		BricksByStack = sumBricks / nStack;
	}
	for (int i = 0; i < nStack; i++) {
		if (nBrick[i] > BricksByStack) minCount += (nBrick[i] - BricksByStack);
	}
	return minCount;
}
// 1: 스택의 개수 nStack과 스택 당 벽돌의 개수를 저장해놓은 배열 nBrick[]를 매개변수로 받는다.
// 2: 앞에서부터 차례로 전체 벽돌 수, 한 스택 당 벽돌 수, 벽돌을 옮기는 최소한의 수
// 3-5: 전체 벽돌 수를 구하기 위해 nBrick의 각 인덱스 값들을 모두 합쳐 sumBricks에 저장
// 6-8: 일정하게 배치할 시에 한 스택 당 벽돌의 개수를 구해 BricksByStack에 저장
// 9-11: BricksByStack을 초과하는 블록의 개수 (옮길 블록의 개수.) (초과하는 만큼만 옮기면 최소이다.)

 

다음은 메인 함수이다.

 

int main() {
//main 함수 영역에서의 선언 - 각 세트 단위
	int nSet = 0, num = 1; // nSet : 세트의 개수, num : 입력받은 스택 수(0이 나오면 종료)
	int min[100] = { 0, }; // 각 세트에서 최소로 움직여야하는 수를 저장한 것. (세트 단위임을 주의!)
	int i = 0;

//while문 영역에서의 선언 - 세트 안의 각 스택 단위
	while (num != 0) {
		cin >> num;
		if (num == 0)break; // 입력받은 스택의 수가 0이면 종료
		int nStack = num; // num에 따라 nStack 설정
		int* nBrick = new int[nStack]; // 각 스택에 들어갈 벽돌을 저장하는 동적 배열 할당.

		for (int i = 0; i < nStack; i++) {
			cin >> nBrick[i];
		}
		++nSet; // 총 세트 수를 셈.

		min[i++] = findMin(num, nBrick); // 각 "세트"에서 최소로 움직이는 수를 저장하는 배열

		delete[] nBrick;
	}
	for (int j = 0; j < nSet; j++) {
		cout << "Set #" << j + 1 << endl;
		cout << "The minimum number of moves is " << min[j] << "." << endl << endl;
	}
}