200810031716

Josh, 문제 풀었다

어제 얘기했던 전선 문제, 지하철 타고 대전역 가는 도중에 답을 찾았다.

step 1. 니가 얘기한대로, 전선을 1개, 2개, 3개, … a개, c개 (c<=a인 임의의 값. a개로 딱 나눠 떨어지지 않을 경우) 묶음으로 나누고, 반대편에서 전구로 하나씩 체크해서 각 묶음을 판별한다.

step 2. 만약 위 c개 묶음이 있으면 하나를 따로 빼서 c-1개로 만들고, 원래 c개와 똑같은 개수의 묶음과 비교해서 각각을 구분한다.

step 3. 각 전선을 Lx, 각 묶음을 Gy라고 하면 아래와 같이 정리됨. G1 = {L1} G2 = {L2, L3} G3 = {L4, L5, L6} … Gc … Ga = {Ln-a, … , Ln}

1) 각 묶음의 첫번째 전선을 다 연결한다. 2) 첫번째 전선을 제외하고 남은 전선에 대해 두번째 전선도 1)과 같은 방식으로 연결한다. 3) 위 과정을 Ga의 마지막 전선만 남을때까지 반복한다. 4) 이제 반대편에 가서 한쪽 단자에 배터리, 한쪽에 전구 연결해가면서 불켜지는지 확인하면 끝.

즉, L1, L2, L4, … Ln-a 를 같이 연결 L3, L5, … Ln-a-1 를 같이 연결 …. Ln 만 남음

반대편에서 (전선)-(배터리)-(전구)-(전선) 식으로 연결해서 불이 켜지면 양쪽 전선은 바로 전에 연결한 것임 L1은 이미 알고 있으므로 L2, L4, … , Ln-a은 모두 identification됨 L2를 알면 L3를 알게 되므로 L5, … , Ln-a-1은 모두 identification됨 L4,L5를 알면 L6를 알게 되므로 … (이하 반복)

위 과정으로 모든 전선을 알 수 있음

• 2008/10/03 17:16 에 작성