정확한 확률에 따른 아이템 드랍

문제

 	아이템 목록이 다음과 같을 때
 	
	등급		아이템		확률		아이템		확률
	-----------------------------------------------------------------------
	5star		A-Item		1%
	-----------------------------------------------------------------------
	4star		B-Item		3%		C-Item		 3%
	-----------------------------------------------------------------------
	3star		D-Item		5%		E-Item		 5%
			F-Item		5%
	-----------------------------------------------------------------------
	2star		G-Item		10%		H-Item		10%
			I-Item		10%		J-Item		10%
	-----------------------------------------------------------------------
	1star	K-Item		38%
	-----------------------------------------------------------------------
	
	**각 아이템이 지정된 확률에 맞게 정확히 나올 수 있도록** 프로그램을 작성하시오.
	ex> 횟수 ? 100		A : 1, B : 3, C : 3, D : 5 .....................
	횟수 ? 1000		A : 10, B : 30, C : 30, D : 50 .................

 

 

---

 

 

제약사항

srand만 사용해서는 정확한 확률을 만들 수 없다.

visual studio에서 제공하는 srand() 함수로 확률 제공을 하면 설정한 확률에 정확히 맞지 않다는 것을 확인할 수 있다.

    동전을 백만 번 던지는 것을 시뮬레이션 하고
	앞면과 뒷면이 나오는 수를 출력하는 프로그램을 작성하라. 
	다음과 같이 각각 앞뒤삭 몇 %씩 나오는지 계산해 출력하라.
	ex> 
		100		번째일 때 ... 앞면 00 % 뒷면 00 %
		1'000		번째일 때 ... 앞면 00 % 뒷면 00 %
		10'000		번째일 때 ... 앞면 00 % 뒷면 00 %
		100'000		번째일 때 ... 앞면 00 % 뒷면 00 %
		1'000'000	번째일 때 ... 앞면 00 % 뒷면 00 %

앞서 이 문제를 풀었는데, 이 문제를 srand로 이용해서 풀면 앞면, 뒷면의 확률이 정확하게 50%로 떨어지지 않는 것을 확인할 수가 있었다.

 

ex) 동전 확률 문제 코드 참고

int main()
{
	srand(time(NULL));

	int front = 0, back = 0;
	bool randNum;
	int unit = 100;

	for (int i = 1; i <= 1'000'000; i++)
	{
		randNum = rand() % 2;
		if (randNum == 1) front++;
		else back++;
		if (i == unit)
		{
			//cout << front << " , " << back << endl;
			cout << setw(6) << i << "번째일 때 앞면 " << (front / (float)unit) * 100 << " %  뒷면 " << (back/(float)unit)*100 << "%\\n";
			unit *= 10;
		}
	}
}

위의 코드 출력 결과

위처럼 정확히 50:50 확률로 나오지 않는다.

따라서, 게임 아이템 드랍과 같이 확률에 굉장히 예민한 분야에서는 사용할 수 없음. 정확한 확률을 위한 설계의 필요성이 나옴.

 

 

설계

1. 100개의 아이템을 담고 있는 배열이 있다.
2. 이 배열에는 각 아이템의 확률만큼의 아이템 개수가 각각 들어가 있다.
3. 이 100개 중에서 랜덤한 index에서 정보를 뽑아내고, 그 index에 담고 있던 정보를 비워주면 100번 돌린 뒤에 이 배열에는 아무것도 안 들어있을 것이다.
4. 따라서 100번을 돌린 뒤에 이 배열에는 아무것도 없을 것이니 다시 채워주는 과정이 필요하다.

 

코드 구현

		#define ITEM_COUNT	11

struct Item
{
	char type;
	int count = 0;
};

const int itemPercent[ITEM_COUNT] = { 1, 3, 3, 5, 5, 5, 10, 10, 10, 10, 38 };

void setItemPercentage(int item[]);

int main()
{
	int item[100];
	int idx = 0;
	int rand_num;
	int unit = 100;
	Item itemCnt[ITEM_COUNT] = { {'A', 0},{'B', 0},{'C', 0},{'D', 0},{'E', 0},{'F', 0},{'G', 0},{'H', 0},{'I', 0},{'J', 0},{'K', 0}};
	
	setItemPercentage(item);

	for (int i = 1; i <= 1'000'000; i++)
	{
		while (1)
		{
			rand_num = rand() % 100;
			if (item[rand_num] != 99)	// 이미 뽑힌 공간이 아니라면 랜덤 돌리는 거 그만함 (뽑아내기 위해)
				break;
		}

		itemCnt[item[rand_num]].count++;
		item[rand_num] = 99;			// 이미 뽑힌 공간이라는 의미로 99 넣음

		if (i % 100 == 0) setItemPercentage(item);

		if (i == unit)
		{
			cout << "횟수 " << std::left << setw(7) << i << "  A: " << itemCnt[0].count << "  B: " << itemCnt[1].count <<
				"  C: " << itemCnt[2].count << "  D: " << itemCnt[3].count << "  E: " << itemCnt[4].count << "  F: " << itemCnt[5].count << 
				"  G: " << itemCnt[6].count << "  H: " << itemCnt[7].count << "  I: " << itemCnt[8].count << "  J: " << itemCnt[9].count << 
				"  K: " << itemCnt[10].count << endl;
			unit *= 10;
		}
	}
}

void setItemPercentage(int item[])
{
	int idx = 0;
	for (int i = 0; i < ITEM_COUNT; i++)
	{
		for (int j = 0; j < itemPercent[i]; j++)
		{
			item[idx++] = i;
		}
	}
}

 

실행 결과