최소 저항 회로
시간 제한2초메모리 제한128 MB
저항값이 1 또는 2인 저항들을 직렬과 병렬로 조합해서 정확히 a/b의 등가 저항을 만드는 데 필요한 최소 저항 개수를 구하고, 16개를 넘으면 -1을 출력합니다.
문제
값이 1인 저항과 값이 2인 저항을 충분히 사용할 수 있다.
여러 저항을 직렬로 연결하면 전체 저항은 각 저항값의 합이 된다. 예를 들어 R1, R2, R3, ..., Rn을 직렬로 연결하면 전체 저항은 R1 + R2 + R3 + ... + Rn이다.
여러 저항을 병렬로 연결하면 전체 저항은 각 저항값의 역수를 더한 뒤 다시 역수를 취한 값이다. 즉 1 / ((1 / R1) + (1 / R2) + (1 / R3) + ... + (1 / Rn))이다.
두 자연수 a와 b가 주어진다. 저항들을 직렬 또는 병렬로 연결해 전체 저항이 정확히 a / b가 되게 하려고 한다. 필요한 저항의 최소 개수를 구하라.
입력
첫째 줄에 두 자연수 a와 b가 주어진다. 두 수는 모두 50,000 이하이다.
출력
첫째 줄에 필요한 저항의 최소 개수를 출력한다. 필요한 저항의 수가 16개보다 크다면 -1을 출력한다.
힌트
6 / 5를 만들려면 먼저 값이 1인 저항과 값이 2인 저항을 직렬로 연결해 값 3을 만든다. 그 결과를 값이 2인 저항과 병렬로 연결하면 된다.