환전소 차익 사이클 탐지
골드 II의견: 0
도시에는 \(N\) 가지 통화가 유통되고 있고, 곳곳에 환전소가 있다. 각 환전소는 어떤 통화 \(a\) 를 다른 통화 \(b\) 로 바꿔 주며, 그 환율 \(r\) 은 통화 \(a\) 한 단위를 통화 \(b\) \(r\) 단위로 바꿔 준다는 뜻이다. 수수료는 없다고 가정한다.
영리한 투자자는 어떤 통화에서 출발해 여러 환전소를 거쳐 다시 그 통화로 돌아왔을 때 처음보다 더 많은 돈을 손에 쥘 수 있는지를 궁금해한다. 그런 환전 경로(닫힌 순환)를 차익 사이클(arbitrage cycle) 이라고 부른다. 즉, 통화들의 순환 \(c_1 \to c_2 \to \cdots \to c_k \to c_1\) 을 따라간 환율의 곱이 \(1\) 보다 크면 차익 사이클이다.
환율표가 주어질 때, 차익 사이클이 하나라도 존재하는지 판정하는 프로그램을 작성하라.
예를 들어 통화가 \(3\) 개이고 \(1 \to 2\) 가 \(1.20\), \(2 \to 3\) 이 \(0.90\), \(3 \to 1\) 이 \(1.10\) 이라면 \(1 \to 2 \to 3 \to 1\) 을 따라간 곱이 \(1.20 \times 0.90 \times 1.10 = 1.188 > 1\) 이므로 차익 사이클이 존재한다.
\(1 \le N \le 400\)
\(0 \le M \le 5000\)
\(1 \le a, b \le N\), \(a \neq b\)
\(0.01 \le r \le 100.00\) (소수점 아래 둘째 자리까지)
첫째 줄에 통화의 수 \(N\) 과 환전소(방향이 있는 환율)의 수 \(M\) 이 공백으로 구분되어 주어진다.
다음 \(M\) 개의 줄에는 각각 세 값 \(a\), \(b\), \(r\) 이 주어진다. 이는 통화 \(a\) 한 단위를 통화 \(b\) \(r\) 단위로 바꿔 주는 환전소가 있다는 뜻이다. \(r\) 은 소수점 아래 둘째 자리까지 주어지는 양의 실수이다.
같은 \((a, b)\) 순서쌍에 대해 서로 다른 환율을 가진 환전소가 여러 개 있을 수 있으며, 이때는 그중 어느 것이든 골라 쓸 수 있다.
차익 사이클이 하나라도 존재하면 YES, 그렇지 않으면 NO 를 한 줄에 출력한다.
3 3
1 2 1.20
2 3 0.90
3 1 1.10
YES
1번 통화 → 2번 통화 → 3번 통화 → 1번 통화로 환전하면 \(1.20 \times 0.90 \times 1.10 = 1.188\) 배가 되어, 시작했을 때보다 많은 돈을 얻을 수 있다. 따라서 차익 사이클이 존재하므로 YES.
2 2
1 2 2.00
2 1 0.40
NO
1번 → 2번 → 1번 환전은 \(2.00 \times 0.40 = 0.80\) 배로 오히려 손해이며, 다른 사이클도 없으므로 차익을 낼 수 없다. NO.
riseoj 작성
출처 Original
평가 및 의견
환전소 차익 사이클 탐지
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
환전소 차익 사이클 탐지