Jungol] 1394 : 양팔저울

문제 주소 : http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=670&sca=4040

나는 이 문제를 수학적으로 생각해서 풀이를 진행했다.

그래서 문제 풀이에 아쉬움이 남는다.(이게 모범 답안일수도 있겠지만, 또 다른 답안이 있으리라..)

좀 더 특별한 방법이 있다면 차후에 다시 생각하여 올려보도록 하겠다.

나는 이 문제를 풀면서 토너먼트 방식을 사용했다.

물건이 몇개가 되더라도 2개씩만 비교할 수 있다는 양팔저울의 특성 상,

N(N>=2)개의 물건 중 가장 질량이 큰 것이 무엇인지 정확히 알아내기 위한 최소한의 시행 횟수는 N-1번이면 된다.

가장 무거운 물건을 찾는 것은 정밀한 측정이 필요가 없기 때문에,

A가 무거운지 B가 무거운지에 대한 정보만 취득하면 되기 때문이다.

그리고 이 정보는 우리에게 2번째로 무거운 물건을 찾는 것에 큰 도움이 된다.

이는 위에 말했던 것처럼 토너먼트 매칭 방식을 떠올리면 이해가 빠를 것이다.

2번째로 무거운 물건을 찾는 것은

우리가 가장 무거운 것을 찾으면서 얻었던 정보를 기반으로 찾아낼 수 있다.

가장 무거운 물건과 가장 마지막으로 비교했던 물건이 유력한 후보일 수 있지만,

이 물건과 비교하는 과정에서 제외되었던 물건 또한 유력한 후보일 수 있다.

이에 대한 예시는 아래 사진과 같다.

물건에 대한 질량값을 측정했을때, 이런 경우도 발생할 수 있다.

최종 단계에서 10과 비교한 물건의 질량은 6이다.

우연히 그것이 두 번째로 무거운 질량을 가진 물건일수도 있다.

그러나, 위의 상황처럼 아닐 수도 있는 유력 후보일 뿐이다.

그렇다면, 가장 무거웠던 물건과 비교한 것들 모두 후보가 될 수 있다. 

그 후보군들에 대해서 가장 무거운 물건을 저울에 다는 시행을 실시하면 된다.

두번째로 무거운 물건을 조사하는 상황에서의 비교 대상에 포함되는 물건의 개수는

전체 물건의 개수가 N이라고 할때 ceil(log2N)개이다.

이를 수식화하면 다음과 같다.

N : N>=2 ; 정수

C : 비교 횟수

C = (N - 1) + (ceil(log2N) - 1)

ex)

N = 2,

C = 1 + (1 - 1)

N = 5,

C = 4 + (3 - 1) = 6

#include <iostream>
#include <math.h>
using namespace std;
int main()
{
	int n;
	int k = 1;

	cin >> n;
	while ((int)pow(2, k) < n)
	{
		k++;
	}
	cout << (n + k - 2);

	return 0;
}