퀴즈 262 5개의 다이아몬드

5개의 다이아몬드의 무게 순위를 정확하게 결정하려면 천칭을 몇번 사용해야 하는가?

퀴즈 263 6개의 다이아몬드

6개의 다이아몬드의 무게 순위를 정확하게 결정하려면 천칭을 몇번 사용해야 하는가?

풀이

5개면 7번, 6개면 10번이 필요하다.

사실 이 문제는 조금 많이 번거로운 문제이긴 하다.

노가다성 방법 말고 어떻게 하면 이 문제를 쉽게 풀 수 있을까?

여기서 말하는 노가다성 방법이란 (a1,a2,a3,a4,a5) 라 두고 직접 재보는 것이다. 이 경우 수형도를 그려보면 [꽤 시간을 투자해야 한다.] 최대 경우의 수가 7개가 나온다.

[4개까지는 이 방법이 쉬운데... 5개 부터는 고려해야 할 상황들이 꽤 된다. ㅠㅠ]

누군가 stackexchange 에 이 문제에 대한 질문을 올렸는데, 링크

여기서 나온 풀이 역시 counting 이다.

흠....

다른 방법으로 이 문제의 일반화된 문제를 풀고 싶어서 논문 검색을 하다가 다음과 같은 논문을 발했다. 링크

흠 근데 저 논문의 section 3 이 지금 이 문제를 말하는 것 처럼 보였는데 답이 틀린데? 내가 잘못 이해하고 있는 건가?

흠 알고리즘, 코딩적 관점에서 한번 접근해 봐야 하나?

이 문제들은 조금 더 생각할 필요가 있어 보인다.