여행(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()