분할 정복 (1) 썸네일형 리스트형 백준 1493 - 박스 채우기 https://www.acmicpc.net/problem/1493 전략 박스 구석부터 채운다. 가능한 한 가장 큰 박스를 채우도록 한다. 가장 큰 박스를 놓지 않으면 다음과 같은 일이 벌어진다. 위 그림의 빨간 부분처럼 어중간하게 빈 영역이 발생하는데 이런 영역은 모서리에 있는 게 최적이고 그렇지 않으면 큰 큐브가 있어도 끼울 수 없는 경우가 있다. 따라서 이 문제는 큐브를 큰 거부터 채워가는 그리디 문제가 된다. 분할 정복 그러면 구석에서 배치할 수 있는 큰 큐브를 배치했다고 해보자. "다음으로 큰 큐브를 어떻게 배치하는가?"가 관심사가 되는데 배치 가능한 영역을 3~4개로 나누는 방법이 있다. 위처럼 큐브를 채우지 않은 영역을 빨간색, 파란색, 초록색 영역으로 나눌 수 있고 재귀적으로 영역을 나눠가며.. 이전 1 다음
