| [ QuizWit ] in KIDS 글 쓴 이(By): constell (나의 꿈) 날 짜 (Date): 1997년05월21일(수) 22시58분44초 KDT 제 목(Title): [답?] 프로그래머. 15벌. 이번주에 월, 화, ... , 일요일까지 입은 셔츠를 A1, A2, ..., A7라고 합시다. 그리고 이번주 월요일에 맡긴 옷들을 B1, B2, ..., Bm (m is unknown yet)이라 하고, 이번주 월요일에 찾아온 옷들을 C1, C2, ..., Cn (n is unknown)이라 합시다. 그런데, 당연한 이야기지만 m = n 이죠. m > n 이면 옷이 점점 줄어들 거고 m < n 이면 맡긴 옷보다 더 많이 찾아온다는 얘기니까. 그래서 B1, ..., Bn이라 하고. 물론 Bi=Bj => i=j, and Ci=Cj => i=j (distinct.) [1] 문제 조건에 따라, '이번주'에 맡긴 B는 '이번주'에는 찾아올 수 없으므로 B intersection C = empty set. [2] 그리고 A = {Ai}, B = {Bi}, C = {Ci}라 합시다. 일단, A1, ..., A7은 distinct [3], 왜냐하면 주 중에 세탁소에 가는 건 월요일인데 그 때 A1를 맡길 수도 없고(찾을수도 없겠지만:>) 그 뒤로는 세탁소에 갈 일도 없으 므로 주중 하루 입었던 셔츠(Ai)를 다시 입을(Aj, i<j) 방법이 없으니까. 그런데, 어떤 Ai도 B의 원소가 될 수 없습니다. 왜냐하면 A1을 입고서 세탁소에 B를 맡겼으니까 A1는 안 되고, B의 옷들은 다음주에야 찾아올 것이므로. 따라서 A intersection B = empty set. [4] 이제 Ai가 C의 원소가 될 수 있는지 봅시다. 일단 A1은 C의 원소가 안 됨(A1을 입고 C를 찾아왔으므로). 그러면 | A intersection C | <= 6이므로 | A union C | >= n + 1 이고. 따라서 | A union B union C | >= 2n + 1. 그러니까 최소한 2n + 1 벌 필요하죠. 이제 n이 최소 몇인지 알아보고, 만약 그 n에 대해 2n + 1 벌로 스케쥴을 짤 수 있으면 충분. 한번 해 보죠 뭐. A1, A2, ..., A7는 이번주에 입은 셔츠들로서, 다음주 월요일 출근길에 맡겨야 합니다(만약 그렇지 않다면, Ai(i>7)인 셔츠가 또 필요하게 되고, 이것은 최소한 Aj(j <= 7)과는 달라야 하므로 another 셔츠가 필요한 셈이죠. 결국 n도 늘어나게 되고). 따라서 어쨌거나 최소한 7벌의 셔츠를 맡겨야 하고, n >= 7 입니다. 그러면 2n + 1 = 15. 이미 위의 argument에서 짐작이 가능하지만, 15벌을 이용해서 다음의 스케쥴이 가능합니다. ___ 0 ~ 6 맡기고, 8 ~ 14 찾아옴. / 월 화 수 목 금 토 일 | 월 화 수 목 금 토 일 | 월 화 수 목 금 토 일 | 월 ... 0 1 2 3 4 5 6 | 7 8 9 10 11 12 13 | 14 0 1 2 3 4 5 | 6 ... 7 ~ 13 맡기고, 0 ~ 6 찾아옴._______/ | 14, 0 ~ 5 맡기고, 7 ~ 13 찾아옴. 다른 식으로 쓰면, 어느 월요일 i + 7 셔츠를 입고 출근하면서, i ~ i + 6 를 맡기고, i + 8 ~ i ~ 14 를 찾아온다. 그 다음주 월요일은 i + 7 셔츠를 입고 출근하면서, i + 7 ~ i + 13 를 맡기고, i ~ i + 6 를 찾아온다. 그 다음주부터는 i를 _감소_ 시키면서 위를 반복(그니까 주기는 2주)한다. (사실 정확하게는 모두들 mod 14를 취해서.. :>) 위의 예로 따진다면 i의 초기값은 0. 따라서 15벌로 가능. 일반적으로는 2n + 1벌. @이미 같은 답이 올라왔네요. :) 누구에게나 꿈이 있다. --------------------- 'Kim Kang-hoe' outside electronic world. Under94@CS@KAIST, constell@eve. |