| [ KAIST ] in KIDS 글 쓴 이(By): kdh709 (푸른하늘) 날 짜 (Date): 2001년 10월 11일 목요일 오후 03시 59분 29초 제 목(Title): [질문] 순서정보만 가지고 숫자 찾기 해결해야 할 문제가 생겼습니다. 고수님들의 의견을 필요로 하네요.. 도와주시기 바랍니다. 문제는 4X4 짜리 행렬에 1부터 16까지의 숫자가 들어있다고 합시다. 물론 임의로요.. 예를 들어 1 4 14 11 10 8 3 5 6 12 2 15 13 7 16 9 그런데, 우리가 알고 있는 정보는 각 행의 순서정보와 각 열의 순서정보입니다. ( r(i,j), c(i,j) ) 입니다. 즉, 첫번째 행의 순서정보는 (1,4,14,11) 이므로 (1, 2, 4, 3) 첫번째 열의 순서정보는 (1,10,6,13) 이므로 (1, 3, 2, 4) 등등... 이와 같이 하면... 오른쪽에 (r,c) 순서로 적습니다 1 4 14 11 1,1 2,1 4,3 3,3 10 8 3 5 4,3 3,2 1,2 2,1 <===> 6 12 2 15 2,2 3,4 1,1 4,4 13 7 16 9 3,4 1,2 4,4 2,2 왼쪽에서 오른쪽으로 가는건 쉽지요.. 그런데, 오른쪽 즉 각 행과 열의 순서정보인 ( r(i,j), c(i,j) )만을 가지고, 과연 왼쪽의 값 1~16까지를 찾아내는 방법이 있을까요? 어떤 scheme, 예를 들어 각 열의 합을가지고 weighting을 준다거나, 을 사용해야, 가능한지 아시는 분 알려주세요.. 그리고 이게 불가능 하다면 어떤 이유에서 그런지 알려주시기 바랍니다. 고수님의 답변 기다립니다. 꾸벅.. |