[퀴즈] 최소한의 이동 거리는?

[이기가byte]

들판에 집이 한 채 있고 그 집에서 1km 떨어진 곳에 창고가 한 채 있는데 집과 창고를 연결하는 100가닥의 전선이 땅속에 매설되어 있다. 전선은 모두 색깔과 굵기가 같다. 집에 있는 전선과 창고에 있는 전선 끝에 아무 표식이 없다. 집에 있는 전선과 같은 전선의 끝을 창고에서 찾아 양쪽 끝에 1에서 100까지 번호를 부착하려고 한다. 집에는 건전지 100여개와 전구 한 개, 넉넉할 만큼의 견출지와 테이프가 있다. 이것들을 이용하여 이 작업을 완수하려면 창고와 집을 몇 번을 왕복해야 할까? 집에서 출발하여 최소한의 이동거리를 구하여라.

[aksiz]

바이너리 인코딩이면 되네요. 2^7 = 128 이니까 7개의 bit 정보를 알면 되죠.
정확히는 집에서 출발해서 창고에 도착하는 순간 7개의 bit이 완성되야 하니, (6*2)+1 = 13km 를 가면 되네요.

바이너리 인코딩 방법은 총 각 전선의 번호를 이진수로 적은 뒤에 맨 오른쪽 비트부터 시작해서 1이면 건전지를 연결하고, 0이면 연결을 안하면 됩니다. (사실 무슨 비트부터 시작하는지는 중요하진 않지만 편의를 위해)
예를들면 9 의 경우 "0001001" 이죠. 처음 갈때(1)는 배터리를 연결하고, 두번째(0)은 연결하지 말고, 세번째(0)도 연결하지 말고, 네번째(1)는 연결하고, ... 이런 식인거죠.

6번왕복+편도 한번이면 7비트를 전부 구할 수 있고, 바이너리 숫자를 다시 십진수로 바꿔서 창고에 있는 전선에 표시해 놓으면 됩니다.

[구명랑]

91개면 딱 한번 왕복 2km로 가능한데 100개라서 한번 더 가야할 듯 싶네요. 3km면 될 듯 싶습니다.

[aksiz]

편도 세번으로 가능하다고요? 배터리가 100여개 정도밖에 없는데도요? 설명을 좀 부탁합니다.

[구명랑]

맞아요. 배터리 생각을 못했네요. 건전지는 극성이 있어서 한 방향 밖에 못가죠. 그렇다면 굳이 3km까지 필요없이 왕복 1회 2km면 될 것 같습니다. 잠시만 생각 정리 좀 할께요.

[구명랑]

처음에 생각했던게 맞았네요. 맞게 생각하고서 배터리를 교류처럼 생각하는 바람에 꼬여버렸어요.

우선 1부터 100까지 라벨을 먼저 붙여놓습니다.

그 다음에 100번 전선에 배터리의 음극을 연결하고 양극에는 나머지 전선을 모두 연결합니다.

그 다음에는 99번 전선에 배터리의 음극을 연결하고 양극에는 1과 100을 제외한 나머지 모두를 연결합니다. 물론 100번째와는 이미 연결되어 있기 때문에 빼는 겁니다.

그 다음 98번 전선에 음극을 연결하고 1, 2번과 99, 100번 전선을 제외한 나머지를 양극에 연결합니다.

이런 식으로 연결하다가 마지막으로 51번 전선에 음극을 연결하고 50번 전선에 양극을 연결하면 끝납니다.

여기까지가 집에서의 작업입니다.

창고에 와서는 다음과 같이 합니다.

하나의 전선을 골라서 다른 전선들 하나씩과 전구를 연결하여 불이 들어오는지를 봅니다.

들어오는 불이 1개밖에 없으면 1번선입니다.

들어오는 불이 2개밖에 없으면 2번선입니다.

쭉 가다가 50번선과 51번선이 모두 50개씩 불이 들어와서 구분할 수 없습니다.

그 다음에 불이 51개가 들어오면 52번선입니다.

불이 52개가 들어오면 53번 선이고 마지막에 99개가 들어오면 100번선입니다.

그렇다면 이제 50, 51번 선만 구분하면 됩니다. 간단하죠. 둘중에 하나를 1번에 연결시켜 놓고 다시 집으로 와서 작업했던 회로 다 치운다음에 1번과 불켜지는 거 찾으면 됩니다.

[구명랑]

생각해 보니 교류라도 별 상관이 없군요. 교류도 극은 존재하니까 같은 극끼리는 전류가 통하지 않죠. 쓸데없는 고민을 했었네요.

[구명랑]

50번과 51번을 창고에서 바로 구분하는 방법을 찾았습니다. 아까 51번에 음극을 50번에 양극을 연결했죠. 그럼 마지막에 창고에서 50번, 51번이 남았을 때 또 다른 건전지를 이용해서 두 선과 전구를 연결합니다. 그래서 불이 들어오면 직렬로 제대로 연결되었다는 뜻이므로 음극쪽이 50번, 양극쪽이 51번입니다. 불이 들어오지 않으면 양극쪽이 50번, 음극쪽이 51번입니다.
이로써 창고안에서 모든 전선의 숫자를 다 찾을 수 있습니다. 그러므로 편도 1회, 1km면 다 찾을 수 있습니다.