05. 공 묶음생각해본 풀이(마지막?)

카테고리가 5번까지 있던데 아마 마지막 문제인것 같네요.


우선 공의 무게는 뒤죽박죽이면 어려울테니 오름차순으로 정렬부터 하고 생각합시다.

공이 1, 4, 6, 8, 11, 12가 있고 차이가 3 이상이어야 한다고 해볼게요.


1짜리 공은 어떤 그룹에 들어갈테니 일단 1이라는 그룹을 만들고 시작합니다.

(현재 그룹 : 1)


4짜리 공은 1이랑 묶일 수 있으니 같이 묶어서 1 4라는 그룹을 만들어봅시다.

근데 앞으로 4보다 큰 수들이 남아있는데 이 그룹에 4가 있는 상황에 1이라는 공이 있다는 사실이 별로 중요하진 않죠.

그냥 대표로 4만 적겠습니다.

(현재 그룹  : 4)


6을 봅시다. 4라는 그룹이 있는 상황에 이 그룹에 6은 포함될 수 없습니다. 따라서 6이라는 그룹을 만들어줍니다.

(현재 그룹 ; 4, 6)


8을 봅시다. 이건 4랑 합쳐질 수 있네요. 일단 합치고 아까랑 같은 이유로 4 그룹의 대표값인 8만 남깁시다.

(현재 그룹 : 8, 6)


11을 봅시다. 이건 8이랑도, 6이랑도 묶일 수 있어요. 둘중 누구랑 묶든 상관 없어 보입니다. 왜냐하면 앞으로 나올 수는 11보다 큰 수들이고, 그 수들도 6, 8중 누구든지 묶일 수 있거든요. 아무나 묶으면 되니 그냥 작은 6쪽에 묶어보겠습니다.

(현재 그룹 : 8, 11)


마지막으로 12는 8이랑 묶으면 됩니다.

(현재 그룹 : 12, 11)


이런식으로 각 그룹에서 제일 큰 값만 들고 있으면서 합칠 수 있으면 아무데나 합치고, 못합치면 새 그룹을 만들면 간단하게 풀립니다!

1 0