ACM 104, Arbitrage

http://acm.uva.es/p/v1/104.html

 

각 국가 간의 환율을 입력으로 제공한다. 이것을 바탕으로 환차익을 거두어야 하는데, 1% 이상 얻을 수 있으면서, 거래 국가는 최소로 해야한다.

1136560873_Australian Voting3.cpp

1136560873_input.txt

1136560873_output.txt

 

이 번 문제는 아주 많은 고민을 했다. 다음과 같은 점을 아주 뒤늦게 생각해냈기 때문이다... 국가가 정점(vertex)이고, 환율이 경로(path)라고 가정하자. 그럼 문제가 쉽게 파악된다. 국가를 가장 적게 거치는 경로를 구하기 위해 Floyd-Warshall 알고리즘이 있다. 여기까지는 생각했으나 교환 법칙이 성립하지 않고, 이로 인해 중간 경로를 활용할 수 없어 FW 알고리즘을 적용할 수 없다고 판단해버렸다. 당연히 이것은 내 실수이며  acm.uva.es의 게시판에서 힌트를 얻어 답을 찾을 수 있었다. 왜냐하면 최단 경로와는 성격이 다르기 때문이다.

 

실 제도 그렇지만, 문제에서도 A->B의 환율과 B->A의 환율이 다르다. 나라가 두 개일 때는 문제가 없어보인다. 그러나 하나만 더 추가해도 문제가 발견된다. A->B->C를 통해 얻은 값과 B->A->C을 통해 얻은 값은 서로 다르다. B->C와 A->C의 환율이 다르기 때문이다.

 

교 환 법칙이 성립하지 않으므로 중간 경로를 활용할 수 없다. 단지 한 번에 한 거래씩 곱하되, 그 시점에서 최대로 얻을 수 있는 이익을 취하면 된다. 예를 들어 다음과 같은 경우가 있다고 하자(테이블이 왜 이렇게 들어왔는지는 문제를 통해 이해하기 바란다).

 

 

1번 국가부터 시작하자. 중간 경로는 2이다. 입력된 값은 trade에 저장해두고, prevData에도 보관한다. curData는 모두 0 값을 가진 채로 시작한다.

 

max ( curData [ 1 ][ 1 ] , prevData[ 1 ][ 2 ] * trade [ 2 ][ 1 ] ) = max ( 0 , 0.651 ) = 0.651

 

두 값 중 큰 쪽을 curData [ 1 ][ 1 ]에 저장한다. 아래 거래도 구해서 curData의 첫번째 값을 취할 수 있다.

 

max ( curData [ 1 ][ 1 ] , prevData[ 1 ][ 3 ] * trade [ 3 ][ 1 ] ) = max ( 0.651 , 0.46 ) = 0.651

max ( curData [ 1 ][ 1 ] , prevData[ 1 ][ 4 ] * trade [ 4 ][ 1 ] ) = max ( 0.651 , 0.7385 ) = 0.7385

 

다른 국가도 이런 식으로 구한다. 그럼 첫번째 단계가 끝난다. 여기까지는 FW 알고리즘과 같다. 그러나 교환법칙이 성립하지 않는 이유를 든 것처럼, 두번째 단계에서 FW 알고리즘을 변형하여 적용하는 것을 볼 수 있다.

 

max ( curData [ 1 ][ 1 ] , prevData [ 1 ][ 2 ] * trade [ 2 ][ 1 ] )

 

여 기서 살펴보자. prevData [ 1 ][ 2 ]에는 어떤 값이 들어있을까? 이전 첫번째 단계에서 구한 최대의 이익값이 들어있다(즉, 1->3->2일 수도 있고 1->4->2일 수도 있다. 물론 그냥 1->2일 수도 있다). 그리고 뒤의 trade [ 2 ][ 1 ]을 주목하자. 중간 결과를 교환할 수 없고 부득이하게 거래를 한번씩만 곱하므로 저런 식으로 표현이 되었다. 따라서 curData의 [ i ][ i ] 원소에는 시작과 끝 나라가 똑같은 거래 결과가 들어있다. 다른 원소에는 해당 경로를 통한 거래의 최대값이 들어 있다.

 

그 럼, 거래를 시작한 국가가 반드시 처음하고 끝에만 등장할까? 알고리즘에서 그런 것을 배제하지 않았으므로, 시작한 국가가 중간에 다시 나올 수도 있다. 이는 테스트 케이스에서도 확인할 수 있다. 왜 curData와 prevData를 따로 사용할까. 위의 예에서도 보았지만 이는 문제의 성질 때문이다. prevData에는 변수명이 가리키듯이 이전 연산 결과가 들어있다. 여기에 trade를 곱하면 새로운 max 값을 얻을 수 있을 것이다. 이 값으로 다시 trade를 곱하면 당연히 잘못된 값이 나올 것이다. 원래 결과에 대해 여러 trade를 곱하여 결과를 얻어야하지, 새로운 max에 대해 다시 trade를 구해서는 안되기 때문이다.

 

이 제 경로 값이 저장된 방식을 설명하면 될 것 같다. 시작과 끝 값은 쉽게 알 수 있다. curData [ i ][ i ] ( 0 <= i < 국가 개수) 원소만을 검색하여 1.01이 넘은 것이 발견되면 그것을 결과로 삼으면 되기 때문이다. 그러면 중간 경로는 어떻게 알 수 있을까. 예를 들어 다음과 같은 거래 순서가 답이라고 가정해보자.

 

1 -> 2 -> 4 -> 1

 

위 의 알고리즘에 따르면 1-4의 결과에 거래 1을 곱해서 얻은 것이 1.01을 넘은 것이다(다시 말하지만, 이전에 구한 최적값에 거래 하나만 곱해서 값을 얻는다). 따라서 1-4의 중간 경로를 조회하면 된다. 주의 사항은 중간 경로가 stage 개수만큼 요구된다는 점이다. 이전에 언급했지만, 어떠한 중간 경로는 유일한 값 만을 가지지 않을 수 있다. 다음 경우를 생각해보자.

 

1 -> 4 -> 1 -> 4 -> 1

 

위 의 값도 당연히 해가 될 수 있다. 따라서 중간 경로를 한 테이블만 가질 경우, 다른 값이 덮어써져 올바른 경로를 얻을 수 없게 된다. 따라서 부득이하게 경로 테이블은 국가 - 1 만큼 필요하다. 소스에서는 이해를 쉽게 하기 위해 국가 수 만큼 경로 테이블을 설정했다. 마지막으로 중간 경로를 얻는 방식은 FW 알고리즘과 동일하나, 경로를 역으로 출력하므로 조금 주의가 필요하다. 재귀 함수를 사용하는 첨부 파일의 소스를 참조하면 쉽게 이해할 수 있을 것 같다.