여행(The Trip) PC/UVa ID: 110103/10137, 인기도: B, 성공률: 보통, 레벨: 1

일년에 한번씩 다른 여행지로 가는 학생 모임이 있다. 그 학생들은 지금까지 인디애나폴리스, 피닉스, 내시빌, 필라델피아, 산호세, 아틀란타를 여행했다. 이번 봄에는 아인트호벤으로 여행을 갈 계획이다.

이 학생들은 여행 경비를 모두 똑같이 부담하기로 합의했지만 돈을 쓸 때마다 나눠서 내는 것은 별로 실용적이지 못하다. 그래서 한명씩 식비, 호텔비, 택시비, 비행기표를 부담하기로 한다. 여행이 끝난후에 각 학생이 지출한 내역을 계산한 다음 1센트 단위 내에서 모든 학생들이 쓴 돈이 같도록 돈을 주고 받는다. 하지만 이전 여행의 경험에 비추어보면 돈을 주고 받는 과정은 정말 지루하고 오랜 시간을 요하는 작업이었다. 지출 내역이 주어졌을 때 모든 학생이 쓴 돈이(1센트 단위 내에서) 똑같아지기 위해 전달되어야 하는 최소 액수를 구해보자.

입력

표준 입력을 통해 여러 번의 여행에 대한 정보가 입력된다. 각 여행은 참가한 학생 수를
나타내는 정수 n으로 구성된다. 이 정수 밑으로는 n개의 줄이 입력되는데, 각 줄에는
달러와 센트 단위로 각 학생이 지출한 경비가 입력된다. 학생수는 1000명을 넘지 않으며
어떤 학생도 $10,000.00 이상 지출하지 않는다. 마지막 여행에 대한 정보 다음 줄에는
0만 들어있는 줄이 입력된다.

출력

각 여행에 대해 각 학생이 사용한 금액이 똑같아지기 위해 전달되어야 하는 금액의 총합을 출력한다.

입력 예

3           
10.00
20.00
30.00
4
15.00
15.01
3.00
3.01
0

출력 예

$10.00
$11.99

Reference ProgrammingChallenges


두번째예제의 답이 $12.00 이 아닌 $11.99 가 되는 이유가 잘 떠오르지 않음. AnswerMe~ --[yong27], 2004-09-15

  • 문제에 '1센트 단위에서 똑같이 되도록 돈을 주고 받는다'라고 되어 있어서 1센트 이하의 값은 무시되는 것 같아요. --[destine], 2004-09-15


[Cee] --[destine], 2004-09-15

   1 #include <iostream>
   2 #include <vector>
   3 using namespace std;
   4 
   5 class solution{
   6 public:
   7         solution(){}
   8         ~solution(){}
   9 public:
  10         void clear()
  11         {
  12                 m_vecCost.clear();
  13                 m_fResult = 0.0;
  14         }
  15 
  16         void add(float fCost)
  17         {
  18                 m_vecCost.push_back(fCost);
  19         }
  20 
  21         void solve()
  22         {
  23                 // 평균을 구하자
  24                 vector<float>::iterator itFloat;
  25                 float fMean = 0.0;
  26                 for( itFloat = m_vecCost.begin(); itFloat != m_vecCost.end(); itFloat++ )
  27                 {
  28                         fMean += *itFloat;
  29                 }
  30                 fMean /= m_vecCost.size();
  31 
  32                 // 주고 받을 돈을 계산한다
  33                 float fDiff = 0.0;
  34                 float fTemp;
  35                 for( itFloat = m_vecCost.begin(); itFloat != m_vecCost.end(); itFloat++)
  36                 {
  37                         fTemp = fMean - *itFloat;
  38                         fTemp *= 100;
  39                         fTemp = (int)fTemp;
  40                         fTemp /=100;
  41                         if ( fTemp > 0 )
  42                         {
  43                                 fDiff += (fTemp);
  44                         }
  45                 }
  46                 m_fResult = fDiff;
  47         }
  48 
  49         float result()
  50         {
  51                 return m_fResult;
  52         }
  53 protected:
  54         vector<float> m_vecCost;
  55         float m_fResult;
  56 };
  57 
  58 
  59 
  60 void main(int argc,char* argv[])
  61 {
  62         int nStudents;
  63         float fCost;
  64 
  65         solution sol;
  66         while( true )
  67         {
  68                 cin >> nStudents;
  69                 if ( nStudents <= 0 || nStudents > 1000 )
  70                         return;
  71 
  72                 sol.clear();
  73         
  74                 for ( int i = 0; i < nStudents; i++ )
  75                 {
  76                         cin >> fCost;
  77                         if ( fCost > 10000.00 )
  78                                 return;
  79                         sol.add( fCost );
  80                 }
  81 
  82                 sol.solve();
  83                 cout << sol.result();
  84         }
  85 }

[Python]--[mgenome], 2006-1-26

요즘 [Python]을 배우는 중인데... 공부 좀 하느라고 퀴즈를 풀어보고 있습니다. 이 문제는 알고리즘을 어떻게 만드느냐가 관건인 것 갈은데, 일단 평균을 구해서 소수점 2째 자리에서 버림을 하고. 그걸로 각 값을 빼서 마이너스가 나오면 마이너스 나온 값만 더해서 절대값을 구했습니다. 초보라서 이렇게 만드는데, 두세시간은 걸린 것 같습니다.

   1 def iterate(money):
   2     return  [caculate(part) for part in money]
   3         
   4 def caculate(part):
   5     ave = sum(part)/len(part)
   6     ave_roundoff = ave - ave%0.01
   7 
   8     result = 0
   9     for ele in part:
  10         a = ave_roundoff - ele
  11         if a > 0: result += a
  12     return "$%.2f" % result
  13   
  14 def main():
  15     money = list()
  16     while 1:
  17         input = int(raw_input())
  18         ele = list()
  19         if input == 0: break
  20         for w in range(input):
  21             ele.append(float(raw_input()))
  22         money.append(ele[:])
  23 
  24     print "\n".join(iterate(money))
  25 
  26 if __name__ == '__main__':
  27     main()

AlgorithmQuiz/TheTrip (last edited 2011-08-03 11:01:12 by localhost)

web biohackers.net