13명이 돈을 모았더니 63만원이 되었다.
이런 상황이라고 합시다. 누가 얼마를 냈을까가 궁금하지 않습니까?
그래서 축의금 계산기를 짜봤습니다. 거창하게 들어갈 것도 없고, 적당히 콘솔 프로그램으로 만들어보죠.
축의금은 일반적으로 한 사람당 3, 5, 10만원을 내므로, for loop 3개로 구성하면 되겠군요.
public static void Main()
{
int total = 63;
int people = 13;
{
int total = 63;
int people = 13;
for(int a=0; a <= (total/3); ++a)
{
for(int b=0; b <= (total/5); ++b)
{
for(int c=0; c <= (total/10); ++c)
{
int s = a*3 + b*5 + c*10;
if (s == total && (a+b+c) == people)
{
Console.WriteLine("3={0}, 5={1}, 10={2}", a, b, c);
}
}
}
}
}
이 정도면 원하는 결과를 계산할 수 있을 듯 합니다.
답은 두 개 뿐이네요.
3=1, 5=12 혹은 3=6, 5=5, 10=2 입니다. 경우의 수가 의외로 적네요. 13명의 이름 명단이 있으면 평소 행실이랑 친분 관계를 고려하면 누가 얼마를 냈는지 쉽게 짐작 가능하겠습니다.
자, 개인적인 호기심은 여기서 끝났는데, 프로그래머의 오기가 발동하는군요. 이 문제를 풀기 위한 좀 더 nice한 해결책은 없을까 궁금합니다. 3중 for 루프가 맘에 걸려요. 사실 이 알고리즘은 자판기에서 거스름돈을 뱉어 내기 위한 알고리즘하고 비슷하죠. 조금 다른 점은 모든 경우의 수를 다 살펴봐야 한다는 점 정도?
축의금의 개수를 가변적으로 만들려면, 재귀 호출을 사용하는 알고리즘이 제일 간단하겠군요.
public static void Main()
{
Recurse(new int[coins.Length], 0, 63);
}
static int[] coins = new int[] { 3, 5, 7, 10 };
static int people = 13;
static void Recurse(int[] key, int depth, int remain)
{
int coin = coins[depth];
int maxLoop = remain / coin;
int[] newKey = (int[])key.Clone();
for (int i = 0; i <= maxLoop; ++i)
{
int newRemain = remain - i * coin;
newKey[depth] = i;
if (depth + 1 == coins.Length)
{
var n = newKey.Aggregate(0, delegate(int c, int r)
{
return c + r;
});
if (n == people && newRemain == 0)
{
StringBuilder sb = new StringBuilder();
for (int j = 0; j < coins.Length; ++j)
{
sb.AppendFormat("{0}={1} ", coins[j], newKey[j]);
}
Console.WriteLine(sb.ToString());
}
}
else
{
Recurse(newKey, depth + 1, newRemain);
}
}
}
{
Recurse(new int[coins.Length], 0, 63);
}
static int[] coins = new int[] { 3, 5, 7, 10 };
static int people = 13;
static void Recurse(int[] key, int depth, int remain)
{
int coin = coins[depth];
int maxLoop = remain / coin;
int[] newKey = (int[])key.Clone();
for (int i = 0; i <= maxLoop; ++i)
{
int newRemain = remain - i * coin;
newKey[depth] = i;
if (depth + 1 == coins.Length)
{
var n = newKey.Aggregate(0, delegate(int c, int r)
{
return c + r;
});
if (n == people && newRemain == 0)
{
StringBuilder sb = new StringBuilder();
for (int j = 0; j < coins.Length; ++j)
{
sb.AppendFormat("{0}={1} ", coins[j], newKey[j]);
}
Console.WriteLine(sb.ToString());
}
}
else
{
Recurse(newKey, depth + 1, newRemain);
}
}
}
얼렁 뚱땅 만들어진 것 같습니다. 7만원짜리 축의금을 추가하면, 가능한 경우의 수가 10개로 확 늘어나는군요. 설마 누가 7만원을 냈겠어. ㅎㅎ
사실 위의 알고리즘도 마음에 쏙 들지는 않습니다. 특히 key를 newKey로 복사하는 부분, 이거 굳이 왜 이렇게 했는지 궁금하지 않으십니까. 그 이유는 parallelize를 염두에 두고 있기 때문입니다. Parallel foreach 구문을 사용해서 돌리면 쿼드 코어 CPU를 100% 활용할 수 있는 축의금 뒷조사 프로그램이 완성될 것입니다.
그러나 .... VS2010을 깔기 귀찮기 때문에 패스.
