예전에 소설(아마 “웃지않은 수학자”라는 이름인듯함)을 읽다가 나온 퍼즐을 풀었던 기억이 있는데,
어제 연구실 세미나가 좀 지루해져서 그걸 생각해놓곤 풀어봤습니다.
1, 2, 3, 4, 5, 6이 적힌 구가 6개가 있는데, 이 구들을 실로 잘 연결해서 목걸이를 만드는데, 연속한 구를 선택해서 그 합이 1~21이 모두 나오게 하는 것
문제는 대충 이렇게 되어있는데, 어제 풀다보니 (사실 가능한 순열이 5!개 밖에 안되기 때문에 brute-force에 가까운걸 경험적으로 잘라내면서 진행하던 터라 시간은 잘 가는듯(…)) 일반적인 해법이 가능하다는 사실을 깨닫게 되었음
뭐 간단한 해법은 이런 녀석인데,
잘 생각해보니 문제의 해법은 아주 간단했다. 합이 7이 되는 상을 3개 만들고, 그냥 연결하고 나면 끝.
일단 1~6, 15~21은 trivial하다. (1~6을 넣거나 빼고 세면 되니)
그 사이는 7인 합이 있으니 인접한 1~6을 7인 쌍에 더하면 모두 나옴 (물론 14는 연결된 2묶음을 합하면됨)
조금 더 큰 문제를 고려해봤는데 (1~8인 구라거나 등등), 역시 짝수개이면 2개씩 묶어서 같은 합이 나오게, 홀수개면 제일 큰 하나의 값과 같은 합이 나오는 묶음들로 나누면 종료 -,-
중학교 땐가 저 소설을 봤을 때는 나름대로 시간이 걸렸던 것 같은데 심심해서[…] 다시 손을 대보니 이건 문제랄 것도 없구나 흑흑
