환차익 거래 탐지
골드 III의견: 0
\(N\)종류의 통화(번호 \(1\)부터 \(N\))와 \(M\)개의 환전 규칙이 있다. 규칙 "\(a\) \(b\) \(r\)" 은 통화 \(a\) 한 단위를 통화 \(b\) \(r\)단위로 바꿀 수 있다는 뜻이다(\(r\)은 양의 실수).
당신은 통화 \(1\)을 들고 시작한다. 여러 번 환전을 거쳐 다시 통화 \(1\)로 돌아왔을 때 처음보다 많은 양을 얻을 수 있는 경로(차익 거래)가 존재하는지 판별하라. 더 일반적으로, 통화 \(1\)에서 환전을 통해 도달할 수 있는 통화들 중에서, 환전을 반복할수록 가치가 무한정 커지는 순환(차익 순환)이 하나라도 존재하면 가능하다.
가능하면 YES, 불가능하면 NO를 출력하라.
\(2 \le N \le 500\), \(1 \le M \le 5{,}000\). 같은 \((a, b)\) 규칙이 여러 개 있을 수 있다.
첫째 줄에 통화 수 \(N\)과 규칙 수 \(M\)이 주어진다. 이어 \(M\)개의 줄에 각각 \(a\), \(b\), \(r\)이 주어진다. \(a\), \(b\)는 정수, \(r\)은 소수점 이하 최대 6자리의 양의 실수이다 (\(1 \le a, b \le N\), \(a \ne b\), \(0.000001 \le r \le 1000000\)).
통화 \(1\)에서 도달 가능한 차익 순환이 존재하면 YES, 아니면 NO를 출력한다.
3 3
1 2 2.0
2 3 2.0
3 1 0.3
YES\(1\to2\to3\to1\) 순환의 환율 곱은 \(2.0\times2.0\times0.3=1.2>1\) 이므로 환전을 반복할수록 가치가 늘어난다. 따라서 YES.
3 3
1 2 2.0
2 3 0.4
3 1 1.0
NO\(1\to2\to3\to1\) 의 곱은 \(2.0\times0.4\times1.0=0.8<1\) 이고 다른 순환이 없어 차익이 불가능하다. 따라서 NO.
riseoj 작성
출처 Original
평가 및 의견
환차익 거래 탐지
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
환차익 거래 탐지