알고리즘 문제해결 전략1권 내용중에 이해가 안되는 부분에 대한 질문이에요. tiro25 1권 136쪽에 책장쌓기 문제에 대한 증명을 위해 귀류법을 사용하셨는데 먼저 책장쌓기 내용은 여러 책장을 쌓아올릴때 각 책장i가 버틸 수 있는 최대 무게와 자신의 무게를 각각 Mi, Wi라 할때 쌓는 방법에 대해서 Mi+Wi에 대해서 정렬해서 큰 순서부터 쌓는다고 하고 이에 대한 증명으로 귀류법을 사용해서 증명하셨어요 책에 귀류법이 반대상황을 가정하고 이에대한 모순을 찾는거라고 나와있고 저도 그렇게 알고있었어요. 그래서 증명하는 부분에서 Mi+Wi가 더 큰 A와 작은 B에 대해서 A가 B위에 올라간 경우 Ma > Mb + Wb - Wa, Mb > Wa + X(X는 A 위에 쌓인 무게) => Ma > X + Wb가 나와서 A상자도 B와 나머지 모든 상자를 지탱할 수 있다는 것을 보여줬는데 이부분이 왜 가정에 대한 모순이죠? 이 때도 Ma+Wa > Mb+Wb를 만족한다면 모순이 아니지 않나요? 답변 부탁드릴게요. 4년 전
0개의 댓글이 있습니다. 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
tiro25
1권 136쪽에 책장쌓기 문제에 대한 증명을 위해 귀류법을 사용하셨는데
먼저 책장쌓기 내용은 여러 책장을 쌓아올릴때 각 책장i가 버틸 수 있는 최대 무게와 자신의 무게를 각각 Mi, Wi라 할때 쌓는 방법에 대해서
Mi+Wi에 대해서 정렬해서 큰 순서부터 쌓는다고 하고 이에 대한 증명으로 귀류법을 사용해서 증명하셨어요
책에 귀류법이 반대상황을 가정하고 이에대한 모순을 찾는거라고 나와있고 저도 그렇게 알고있었어요.
그래서 증명하는 부분에서 Mi+Wi가 더 큰 A와 작은 B에 대해서 A가 B위에 올라간 경우
Ma > Mb + Wb - Wa, Mb > Wa + X(X는 A 위에 쌓인 무게)
=> Ma > X + Wb가 나와서 A상자도 B와 나머지 모든 상자를 지탱할 수 있다는 것을 보여줬는데
이부분이 왜 가정에 대한 모순이죠? 이 때도 Ma+Wa > Mb+Wb를 만족한다면 모순이 아니지 않나요?
답변 부탁드릴게요.
4년 전