조합?.. 문제 인 것 같습니다(확실한지는 모릅니다)
저는 조합으로 풀었기에 그렇게 생각했습니다.
다만 책의 풀이와 는 달랐습니다.
저도 저의 풀이가 있긴 한데 제 풀이를 한지 한 1년 전이 된 거 같아서 잘 기억이 안나지만 시간 나는데로 제 풀이를 복기 해서라도 다시 올릴 생각은 있습니다.
당장 풀이가 기억이 안나니 책의 풀이를 올릴 수도 있겠습니다.
추가로, 현재 제가 수험생이고 인터넷을 잘 안하는지라 여기서 풀이를 올려 주셨을 경우에 제가 잘 확인 하지 못할 수도 있다는 점 미리 사과드립니다.
16일??
아닙니다. - dc App
7일??
넵 맞습니다! 풀이 보여주실 수 있을까 합니다! - dc App
하한이 7인건 어떻게 잘 했는데 실제 예시에 오류가 있다는걸 알앗음.. 일단 하한이라도 보임 사람 n명이 있을때 1~n명끼리 방문할때 필요한 최소 일수를 a_n이라고 함 처음에 k명이 다른 집을 방문함 일반성을 잃지않고 1~k번이 k+1~n번을 방문한다고 침 이 때 남은 방문은 1~k끼리 방문하는것(=a_k), k+1~n끼리 방문하는것(=a_n-k), n+1~k이 1~n번을 방문하는것임 이 때 최소한 max(a_k, a_n-k)번은 더 해야함을 알 수 있음 max(a_k, a_n-k)번으로 나머지를 전부 처리할수 있다면 a_n=(k=1~n-1) min( max(a_k, a_n-k)+1 )이 되고 a_30=7이 됨 나머지를 전부 처리할수있는 방법을 찾았다고 생각했는데 자세히 보니 틀렸고 방법이 생각도 안남
스페르너 정리 쓰면 될즛
good 그렇게도 풀려요