[TopCoder] 키위 주스(KiwiJuiceEasy) 분석 및 풀이 Ruin 공방 - 알고리즘

* 문제 번호 *
SRM478 Div2 Lv1

* 문제 유형 *
시뮬레이션

* 사용 언어 *
C++

* 풀이 상태 *
SUCCESS

* 소요 시간 *
15분






* 나의 전략 *
탑코더 알고리즘 트레이닝에서 처음 푼 기념비적인 문제.

그렇게 어렵지는 않은 문제이다.

붓는 병과 부어지는 병 두 개를 가지고 서로의 용량을 비교해보면 되는 것.

하지만 책에서 소개하는 모범 답안은 조금 더 깔끔하다. (뒷 내용에서 보기로 한다)

* 나의 시도 *

 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <algorithm>
#include <vector>

using namespace std;

class KiwiJuiceEasy{
public:
vector<int> thePouring(vector <int> capacities, vector <int> bottles, vector <int> fromId, vector <int> toId)
{
for(int i = 0; i < fromId.size(); i++)
{
int temp = 0;

if(bottles[toId[i]] == capacities[toId[i]]) continue;
if(bottles[fromId[i]] == 0) continue;

if(bottles[toId[i]] + bottles[fromId[i]] <= capacities[toId[i]]) {
temp = bottles[fromId[i]];
bottles[fromId[i]] = 0;
bottles[toId[i]] += temp;
} else {
temp = bottles[toId[i]];
bottles[toId[i]] = capacities[toId[i]];
bottles[fromId[i]] -= (capacities[toId[i]] - temp);
}
}

return bottles;
}
};



* 실패 or 고민 원인 *
특별한 고려 사항 없었음.


* 정답 코드 - TopCoder 알고리즘 트레이닝 *

 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <algorithm>
#include <vector>

using namespace std;

class KiwiJuiceEasy {
public:
vector<int> thePouring(vector<int> capacities,
vector<int> bottles, vector<int> fromId,
vector<int> toId) {

for (int i = 0; i < fromId.size(); i++) {
int sum = bottles[fromId[i]] + bottles[toId[i]];
bottles[toId[i]] = min(sum, capacities[toId[i]]);
bottles[fromId[i]] = sum - bottles[toId[i]];
}

return bottles;
}
};




* 풀이 분석 *
랭커인 저자가 실전에서 제공한 풀이.

보는 순간 참 아름답다고 느낀 코드였다.

저자의 설명은 다음과 같다.

처음 이동량을 생각했을 때 조건 분기에서 실수가 발생할 수 있다고 생각했습니다.
따라서 이동량을 무시하고 옮길 주스와 기존 주스의 양의 총합이 일정하다는 것과 옮길 주스는 주스 총량과 기존 주스 병의 용량 중에 작은 값이 된다는 것을 이용하기로 했습니다.
이를 이용하면 주스의 양을 다음과 같이 나타낼 수 있습니다.

기존 주스 : "옮길 주스와 기존 주스의 총합" 과 "기존 주스 병의 용량" 에서 작은 값
옮길 주스 : "옮길 주스와 기존 주스의 총합" 에서 위의 값을 제외한 값

이런 발상으로 실수를 줄여나가는 것이 중요합니다.


단순하지만 그 단순한 생각으로 코드의 반복문을 상당히 줄여 놓았다.

시뮬레이션도 똑똑해야 바보 같은 실수를 안할 수 있는 것이다.

실제로 내 코드에서는 반복문에 유인한 실수가 몇 번 발생했었다.


* 이론 전개 *
알고리즘 문제의 기본 형태는 시뮬레이션과 전체 탐색이다.

대부분의 문제가 이 풀이들로 풀 수 있으며, 이게 통하지 않는 - 실행 시간이 넘어가거나 너무 많은 경우의 수 - 문제는 어려운 문제라고 할 수 있겠다.

먼저 시뮬레이션에 대해서 정리해보자.

이번 문제에서 저자가 강조한 것은 세 가지이다.

1. 문제를 이해했다면 손으로 계산해보세요
사람은 손을 움직이지 않고 머리로만 생각하면 표면적인 부분까지만 생각할 수 있습니다.
구체적으로 어떤 때에 어떻게 된다는 것을 생각하며 문제를 이해해보세요.
또한, 어떤 코드를 작성할지 생각나도 곧바로 코드를 입력하지 말고 누락된 부분이 없는지 체크하세요.

2. 코딩이 오래 걸린다면 다시 한 번 손으로 생각해보세요.
1번과 같은 내용이지만 많은 것을 생각하고 코드를 작성해도 예상하지 못한 곳에서 문제가 발생할 수 있습니다.
이 때는 코드작성을 중지하고 문제를 다시 한 번 생각해보세요.
이런 습관을 들이지 않으면 간단한 문제를 처리해도 나중에 분명 문제가 발생합니다.

3. 조건문을 되도록 조금 사용하세요.
이번 문제에서는 Example에서 모든 상황을 제공했습니다.
하지만 모든 문제가 Example 에서 모든 상황을 제공하는 것은 아닙니다.
따라서 가능한 조건문을 조금 사용하여 버그를 줄이세요.
버그를 줄여야 TopCoder 에서 매우 중요한 System Test 를 통과할 가능성이 높아집니다.


셋 다 일리 있는 말이다.

물론 저자가 다른 복잡한 방법을 피하기 위해 꽤 많은 조건문을 중첩하는 경우도 있었지만...

(더 복잡해지는 것을 피하기 위해 그런 것 같다)

여태까지 노트로 끄적이는걸 안한 건 아니지만 좀 소홀했다는 것은 인정한다.

이제부터는 손을 좀 더 자주 사용하기로 하자.



통계 위젯 (화이트)

18
50
14720