2018년 4월 15일 일요일

금액계산 경우의 수 [C 언어]

#include 
// 금액 맞추기
// 브루트포스 / 재귀
// 일정금액을 1,2,5,10,20,50 만원으로 계산 가능 가짓수.


void brute(int* bills, int money) {
  int i0, i1, i2, i3, i4; // 각 계산 후 남은 수.
  int count = 0;
  for (i0 = money; i0 >= 0; i0 -=bills[0])
    for (i1 = i0; i1 >= 0; i1 -= bills[1])
      for (i2 = i1; i2 >= 0; i2 -= bills[2])
        for (i3 = i2; i3 >= 0; i3 -= bills[3])
          for (i4 = i3; i4 >= 0; i4 -= bills[4])
            if (i4 % bills[5] == 0)
              count++;
              
  printf("count = %d\n", count);
}

int better(int* bills, int n, int money)
{
  int count = 0, i;
  
  if (n == 1) {
    if (money % bills[0] == 0)
      return 1;
    else
      return 0;
  }

  int len = money / bills[n-1];
  for (i = 0; i <= len; i++) {
    count += better(bills, n-1, money - (bills[n-1] * i));
  }
  
  return count;
}

int main(void) {
  int bills[6] = {1,2,5,10,20,50};
  int money = 100; // res = 4562
  int numberOfBills = 6;
  
  brute(bills, money); 
  // printf("better way : %d\n", better(bills, numberOfBills, money));
  
  return 0;
}

댓글 없음 :

댓글 쓰기