| [ QuizWit ] in KIDS 글 쓴 이(By): cdpark (박종대) 날 짜 (Date): 1996년09월09일(월) 14시30분02초 KDT 제 목(Title): Re: 고기산적을 놓고 다투는 두 사람 고기 산적을 왼쪽부터 차례대로 ABABAB 식으로 번호매김을 합니다. 그럼 모든 A 조각의 합과 모든 B 조각의 합 중에서 큰 쪽을 먹기로 작정을 합니다. (당연히 최소한 절반을 언제나 먹을 수 있죠..) 이때 먹기로 한 조각을 A 조각이라고 합시다. 그럼 맨 왼쪽의 A 조각을 먹었을 때에... 상대방은 B 조각밖에 선택의 여지가 없습니다. (왼쪽이든, 오른쪽이든 모두 B 조각이므로...) 이제 나는 무조건 상대가 먹는 쪽에서 먹으면, 모든 A 조각을 독식(!)할 수 있게 됩니다. 물론 이 방법이 최선의 전략은 아니지만, 최소한 상대보다 손해보지는 않는 전략입니다. PS1: 무조건 왼쪽과 오른쪽 중에서 큰 쪽을 먹는 전략은 실패할 수도 있습니다. 예) [2, 1000, 3, 1].. PS2: 최선의 전략은 O(n^2) 사간에 동적 계획법을 사용하여 구할 수 있습니다. -- 박종대 |