[알고리즘문제] 컨테이너 포장

[알고리즘문제] 컨테이너 포장

Question.

우체국에서는 해외로 나가는 소포들을 컨테이너에 담아서 해외로 보냅니다. 하루 분의 짐은 한꺼번에 모아서 (하나 또는 여러 개의) 컨테이너에 나누어 담습니다. 각각의 컨테이너에 실린 짐의 무게는 110kg을 넘을 수 없습니다. 무게의 합이 110kg이하인 경우에는 두 개의 짐도 실을 수 있습니다. 하지만 한 컨테이너에 세 개 이상의 짐은 실을 수 없습니다. 우체국에서는 운송비를 줄이기 위해서 무게 합이 110kg을 넘지 않으면 두 짐을 g나 컨테이너에 실기로 하고 몇 개의 컨테이너가 필요한지 알고 싶습니다.  당신이 할 일은 우체국을 도와서 최소로 필요한 컨테이너의 수를 구하는 프로그램을 작성하는 것입니다.

입력 형식
입력 파일의 이름은 INPUT.TXT이다. 첫 줄에 운송할 짐의 수 n이 입력된다. n은 1,000 이하인 정수이다. 둘째 줄에는 n 개의 짐의 무게가 입력된다. 무게는 정수로 주어지며, 이들 사이에는 공백이 있다.

출력 형식
출력 파일의 이름은 OUTPUT.TXT이다. 첫째 줄에 최소로 필요한 컨테이너의 수를 출력한다.

입력과 출력의 예

INPUT.TXT
6
30 100 80 70 45 40

OUTPUT.TXT
4

Answer.

처음 입력받은 짐들을 차례대로 두개씩 비교하여 최적의 무게(110kg)가 되거나 또는 그 무게에 근접하였을 때, 그 짐들을 제거하면서 컨테이너 수를 증가하는 방식으로 문제 해결.

void CalculateContainerNumber()
{

// weightSum : 두 짐의 무게의 합,

// oldWeightSum : 이전의 무게의 합을 저정할 임시 변수,

// baggagePoint : 최적의 무게합을 이루는데 사용된 짐(두번째 : j)의 번호
int weightSum = 0, oldWeightSum = 0, baggagePoint = 0; 
bool flag; // 임시 체크 변수

for(int i = 0; i < baggageNumber; i++)
{

if(baggageList[i] == 110) // 짐 하나가 110kg이라면

{

baggageList[i] = 0; // 그 자리에 0으로 채우고
containerNumber++; // 컨터에너 수 하나 추가
continue; // 다음으로 이동  

}

if(baggageList[i] == 0) // 짐의 무게가 없다면 (이미 컨테이너에 실었기 때문에 0이다. 이미 계산되었음) 
    continue; // 다음으로 이동

 

oldWeightSum = 0; // 임시 변수들 초기화
baggagePoint = -1;
flag = false;

for(int j = i+1; j < baggageNumber; j++)
{

if(baggageList[j] == 0) // 짐의 무게가 없다면 (이미 계산되었음)
    continue; // 다음으로 이동

weightSum = baggageList[i] + baggageList[j]; // 두 짐의 무게의 합을 구한다.
   
if(weightSum == 110) // 무게의 합이 110kg이라면 (가장 최적의 무게이므로 다음 짐과 비교할 것 없이 바로 통과)
{

baggageList[i] = baggageList[j] = 0; // 두 짐을 실었으므로 0값으로 채운다. 
containerNumber++; // 컨테이너 수 증가
flag = true; // 아래에서 중복 체크되는 것을 막기 위해
break;

}

if(weightSum > 110) // 두 짐의 무게의 합이 110kg을 넘었다며 컨테이너에 실을 수 없으므로
    continue; // 다음 짐과 다시 비교한다.

if(weightSum > oldWeightSum) // 기존의 짐(i)과 새로운 짐(j)과의 합계가 110kg에 더 가깝다면
{

baggagePoint = j; // 현재 짐의 번호를 최적의 짐 번호에 저장
oldWeightSum = weightSum; // 임시(최적의) 짐 무게 변수에 새로운 짐과의 무계 합을 저장한다.

}

}

if(flag == false) // 무게의 합이 110kg이 아닌 110kg에 가장 근접한 무게일 경우
{

if(baggagePoint < 0) // 오직 하나의 짐만을 실어야 된다면 (두개의 합이 모두 110kg을 넘었을 경우)
    baggageList[i] = 0; // 하나의 짐만 0으로 바꾼다.
else if(j == baggageNumber) // 두개의 짐을 실어야 된다면 (두개의 합이 110kg보다 작으면서 가장 근접한 경우)
    baggageList[i] = baggageList[baggagePoint] = 0; // 두개의 짐을 0으로 바꾼다.

containerNumber++; // 컨터에너의 수를 하나 증가시킨다.

}

}

}

파일 내려 받기 (소스 파일, 실행 파일, 입력/출력 샘플 파일)

container.zip