int Table::select(int &r, int &g, int &b){    //select함수는 풍선의 갯수를 받아서 당장 테이블을 꾸미는데 어떤 풍선을 사용할지에 대해 결정한다.
 if (r >= g && g>= b){        //가장 많은 풍선이 가장 가치가 없으므로 2개를 쓰고 나머지 두 풍선중 가치없는 풍선에서 하나를 사용해 테이블 하나를 꾸민다.
  if (r >= 2)
   r -= 2, g -= 1;
  else if (r == 1)
   r -= 1, g -= 1, b -= 1;
 }
 else if (r >= b && b >= g){
  if (r >= 2)
   r -= 2, b -= 1;
  else if (r == 1)
   r -= 1, g -= 1, b -= 1;
 }
 else if (g >= r && r >= b){
  if (g >= 2)
   g -= 2, r -= 1;
  else if (g == 1)
   r -= 1, g -= 1, b -= 1;
 }
 else if (g >= b && b >= r){
  if (g >= 2)
   g -= 2, b -= 1;
  else if (g == 1)
   r -= 1, g -= 1, b -= 1;
 }
 else if (b >= r && r >= g){
  if (b >= 2)
   b -= 2, r -= 1;
  else if (b == 1)
   r -= 1, g -= 1, b -= 1;
 }
 else if (b >= g && g >= r){
  if (b >= 2)
   b -= 2, g -= 1;
  else if (b == 1)
   r -= 1, g -= 1, b -= 1;
 }
 return r, g, b;  //테이블 하나를 꾸미고 남은 풍선의 갯수를 리턴해준다.
}

 

설명하자면 풍선이 세종류가 있는데 r(red) g(green) b(blue) 이렇게 있습니다. 테이블을 꾸미는데 같은 색상의 풍선을 세번 사용하면 안됩니다.

즉 rrg rrb ggr rgb 이런건 되도 rrr, ggg, bbb이렇게는 안되는거지요.

greedy algorithm이라 매순간순간에 따라 판단을 하는데요,

예를 들어 8 1 1 이렇게 풍선이 있으면 가장 많은 red풍선에서 2개를 빼고 그다음 큰 풍선에서 1을 뺴서 테이블 하나를 꾸미고 남은 숫자를 리턴해서 다시 함수를 부르는 구조로 짰습니다.

일단 조건문이 너무 많기도 하고 이렇게 짜는 것이 최선이라고 생각은 드는데 혹시 다른방법이 있을까요?

전 조건문을 줄이기 위해서 세 숫자 중에 최대값을 뽑아서 2를 빼고 그런식으로 할려고 했는데 그럼 변수를 하나 더 만들어야 하기도 하구요.

Codeforces 에 있는 문제인데 답은 구해지지만 조금 더 효율성을 높이고 싶어서 질문합니다.

 

codeforces link 첨부하겠습니다.