1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230
|
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
struct Job{
int *DayNum ;
int *Penalty;
};//각 일에 대해 걸리는 시간과 벌금
bool CheckJobNum(int OrderNum);
bool CheckDayNum(int DayNum);
bool CheckPenalty(int Penalty);
int Factorial(int num);
void NumToArray(int num, int numarr[]);
void Swap(int &a, int &b);
void string_permutation(string& orig, string& perm, string *permstr);
string NumString(int num);
int ComputePenalty(Job JobArr[], string JobOrder, int JobNum);
void BubSortStr(string Order[], int Penalty[]);
int main()
{
/*
각 일의 기한과 늦었을 때의 벌금을 저장하고
문제에 제시된 값을 초과하거나 미달했을 떄,
에러 메세지를 띄우게 한다
*/
int JobNum;
//Check whether Number of orders are between 1 and 1000
do{
cout << "The number of orders: ";
cin >> JobNum;
if(CheckJobNum(JobNum) == false){
cout << "Error!!" << endl;
continue;
}
else
break;
}while(1);
int CaseNum = Factorial(JobNum);
Job *JobArr = new Job[JobNum];//여러 Job에 대한 정보를 저장하기 위해서 JobNum개의 배열을 만든다.
string *Order = new string[CaseNum];//순서를 저장하기 위한 배열을 만든다.
int *CasePenalty = new int[CaseNum];
for(int i = 0; i < JobNum; i++)
{
JobArr[i].DayNum = new int;//Number of days to finish
JobArr[i].Penalty = new int;//Penalty for each day
}//Assigning memory space in Heap Segment
//Check whether DayNum is between 1 & 2000
for(int i = 0; i < JobNum; i++)
{
cout << "How many days are taken for job " << i + 1 << "? ";
cin >> *(JobArr[i].DayNum);
if(CheckDayNum(*(JobArr[i].DayNum)) == false){
cout << "Error!!" << endl;
i--;
continue;
}
//Check whether Penalty is between 1 & 10000
for(int j = 0; j < 1; j++){
cout << "Daily penalty for job " << i + 1 << "? ";
cin >> *(JobArr[i].Penalty);
if(CheckDayNum(*(JobArr[i].Penalty)) == false){
cout << "Error!!" << endl;
j--;
continue;
}
}
}
/*
여러 순서를 만들기 -> 순열을 이용한다.
각 순서에 대해서 벌금을 계산하고
제일 적은 것을 Bubble Sort로 찾는다.
*/
string orgstr = NumString(JobNum);
string voidstr;
string_permutation(orgstr, voidstr, Order);
//여기까지가 여러순서를 찾는 과정
for(int i = 0; i < CaseNum; i++)
cout << Order[i] << endl;
//각 경우의 벌금을 계산해서 저장
for(int i = 0; i < CaseNum; i++)
CasePenalty[i] = ComputePenalty(JobArr, Order[i], JobNum);
/*
BubSortStr(Order, CasePenalty);
cout << "The order of jobs should be : " << endl;
for(int i = 0; ; i++)
{
cout << Order[i] << endl;
if(CasePenalty[i] < CasePenalty[i + 1])
break;
}
*/
//Deleting memory space in Heap Segment
for(int i = 0; i < JobNum; i++){
delete JobArr[i].DayNum;
delete JobArr[i].Penalty;
}
delete [] JobArr;
delete [] Order;
delete [] CasePenalty;
system("pause");
return 0;
}
bool CheckJobNum(int JobNum)
{
if((JobNum < 1) || (JobNum > 1000))
return false;
else
return true;
}
bool CheckDayNum(int DayNum)
{
if((DayNum < 1) || (DayNum > 2000))
return false;
else
return true;
}
bool CheckPenalty(int Penalty)
{
if((Penalty < 1) || (Penalty > 10000))
return false;
else
return true;
}
int Factorial(int num)
{
int total = 1;
while(num > 0)
{
total *= num--;
}
return total;
}
void Swap(int &a, int &b)
{
int temp;
temp = a;
a = b;
b = temp;
}
//1부터 n까지의 숫자가 나열 될 수 있는 모든 가능성을 오름차순으로 찾아 문자열(string)배열에 저장한다.
void string_permutation(string& orig, string& perm, string *permstr)
{
static int k = 0;//재귀함수가 호출되어도 k의 값은 계속 유지된다
if(orig.empty())
{
permstr[k++] = perm;
return;//baseline for recursion
}
for(int i=0;i<orig.size();++i)
{
string orig2 = orig;
orig2.erase(i,1);
string perm2 = perm;
perm2 += orig.at(i);
string_permutation(orig2, perm2, permstr);
}
}
//1부터 n까지의 숫자를 아스키코드로 변환해서 문자열로 만든다.
string NumString(int num)
{
char *NumStr = new char[num + 1];
for(int i = 0; i < num; i++)
{
NumStr[i] = i + 1;
}
NumStr[num] = '\0';//문자열임을 인식하기 위해서는 마지막에 널문자가 삽입되어야 한다.
string ResultStr(NumStr);
delete [] NumStr;
return ResultStr;
}
int ComputePenalty(Job JobArr[], string JobOrder, int JobNum)
{
int TotalPenalty = 0;
int TotalDay = 0;
int k = 0;
for(int i = 0; i < JobNum - 1; i++)
{
for(int j = 0; j < k + 1; j++){
TotalDay += (*JobArr[JobOrder.at(j) - 1].DayNum);
k++;
}
TotalPenalty += (*JobArr[JobOrder.at(i + 1) - 1].Penalty)*(TotalDay);
}
return TotalPenalty;
}
void BubSortStr(string Order[], int Penalty[])
{
int size = sizeof(Penalty)/sizeof(int);
for(int k = 0; k < size; k++)
for(int i = 0; i < size - 1 - k; i++)
if(Penalty[i] > Penalty[i + 1])
{
int temp = Penalty[i];
Penalty[i] = Penalty[i + 1];
Penalty[i + 1] = temp;
string tempstr = Order[i];
Order[i] = Order[i + 1];
Order[i + 1] = tempstr;
}
}
|