이 문제에서는 세 개의 정수 값 W, n, m이 주어집니다. 각각 벽의 길이 W, 선반의 크기 n과 m을 의미하며, 우리의 목표는 선반 배치 문제(Fitting Shelves Problem)를 해결하는 프로그램을 만드는 것입니다.
핵심 요구 사항은 선반을 배치한 뒤 남는 공간을 최소화하는 것입니다. 여기에 보조 조건으로 제작 비용이 고려되는데, 일반적으로 큰 선반이 비용 대비 효율적이므로 큰 선반에 우선순위를 두어야 합니다.
출력은 아래 형식을 따릅니다.
[n 크기 선반 개수] [m 크기 선반 개수] [남은 공간]
문제 이해하기
예시를 통해 문제를 살펴보겠습니다.
입력: W = 12, n = 5, m = 3 출력: 0 4 0
설명
길이가 3인 선반을 정확히 4개 설치하면 총 길이는 4 × 3 = 12가 되어 벽 전체를 빈틈없이 채울 수 있습니다. 따라서 설치 후 남는 공간은 0입니다.
해결 접근 방법
가장 직관적인 해결책은 브루트 포스(완전 탐색) 방식입니다. 벽에 선반을 배치할 수 있는 모든 조합을 하나씩 검사하면서, 남는 공간을 최소화하거나 없애는 조합을 찾아냅니다.
보조 조건을 반영하기 위해 탐색에 규칙을 둡니다. 남는 공간이 동일한 경우에는 더 큰 선반을 더 많이 사용하는 조합을 선택해 큰 선반에 우선순위를 부여합니다. 이렇게 하면 최적해에 가능한 한 많은 큰 선반이 포함되도록 보장할 수 있습니다.
알고리즘 동작 원리
- 먼저 m 크기 선반만으로 벽을 최대한 채우고 남는 공간을 계산합니다.
- 반복문을 통해 n 크기 선반을 하나씩 늘려가며, 남은 길이를 다시 m 크기 선반으로 채웁니다.
- 매 단계마다 남는 공간을 계산해, 기존 최솟값보다 작거나 같으면 정답 조합을 갱신합니다.
- 모든 경우를 확인한 뒤 최적의 조합과 남는 공간을 출력합니다.
이 알고리즘의 시간 복잡도는 O(W / n)으로, 벽의 길이를 n씩 줄여가며 탐색하기 때문에 매우 효율적입니다.
구현 예제
아래 프로그램은 위 접근 방법이 실제로 어떻게 동작하는지 보여줍니다.
#include <bits/stdc++.h>
using namespace std;
void solveFittingShelves(int wall, int m, int n){
int numM = 0, numN = 0, minSpaceLeft = wall;
int p = wall/m, q = 0, rem = wall%m;
numM = p;
numN = q;
minSpaceLeft = rem;
while (wall >= n) {
q += 1;
wall = wall - n;
p = wall / m;
rem = wall % m;
if (rem <= minSpaceLeft) {
numM = p;
numN = q;
minSpaceLeft = rem;
}
}
cout<<numM<<" "<<numN<<" "<<minSpaceLeft<<endl;
}
int main(){
int W = 29, m = 3, n = 9;
cout<<"Length of wall : "<<W<<endl;
cout<<"Length of shelves : "<<m<<"\t"<<n<<endl;
cout<<"Optimal Shelves fitting : ";
solveFittingShelves(W, m, n);
return 0;
}
실행 결과
Length of wall : 29 Length of shelves : 3 9 Optimal Shelves fitting : 0 3 2
벽의 길이가 29일 때, 길이가 9인 선반 3개를 배치하면 총 27을 차지하고 남는 공간은 2가 되어 최소가 됩니다. 이처럼 완전 탐색을 활용하면 주어진 조건을 만족하는 최적의 선반 배치를 손쉽게 구할 수 있습니다.