왕의 시찰
면접 대비시간 제한1초메모리 제한512 MB
동전 개수 세 개가 주어질 때, 매초 서로 다른 두 상자에 동전을 하나씩 넣어 세 상자의 개수를 같게 만드는 최소 시간을 구한다.
문제
아주 먼 옛날 왕국의 국고에 문제가 생겼다. 왕이 시찰을 나서기 때문이다. 왕은 질서를 좋아하는 것으로 알려져 있다. 그래서 국고 관리인은 왕국의 금화를 보관하는 세 개의 상자를 정리해야 한다. 상자를 살펴보니 각각 , , 개의 금화가 들어 있었다. 하지만 왕은 세 상자에 같은 수의 금화가 들어 있기를 바랄 것이 분명하다.
금화의 수를 같게 만들기 위해 국고 관리인은 두 손으로 금화를 더 넣기 시작했다. 그는 매초 서로 다른 두 상자를 골라 각각에 금화를 한 개씩 더 넣는다.
국고 관리인이 상자의 금화 수를 같게 만드는 데 몇 초가 필요한지 구하시오.
입력
입력은 세 줄로 이루어진다.
첫째 줄에는 정수 가 주어진다.
둘째 줄에는 정수 가 주어진다.
셋째 줄에는 정수 가 주어진다 ().
출력
국고 관리인이 상자의 금화 수를 같게 만드는 데 필요한 최소 시간(초)을 정수 하나로 출력한다.
힌트
첫 번째 테스트에서 가능한 최적 전략 하나는 다음과 같다. 먼저 1번과 3번 상자에 금화를 한 개씩 넣고, 그다음 1번과 2번 상자에 금화를 한 개씩 넣고, 다시 1번과 2번 상자에 금화를 한 개씩 넣는다.
두 번째 테스트에서는 모든 상자에 이미 같은 수의 금화가 들어 있다.