백준 23816 (C++) 옷걸이걸이걸이

최초 업로드: 2025-08-22 01:27:49

최근 수정 시간: 2025-08-22 01:28:13

게시자: rlatjwls3333

카테고리: 백준

# [Gold III] 옷걸이걸이걸이

[문제 링크](https://www.acmicpc.net/problem/23816)

## 문제 설명

옷장을 정리해야 하는데 옷이 너무 많아 옷장 바닥에 흘러넘친다. 옷걸이를 걸 수 있는 위치는 $N$개고, 옷걸이는 $M$개가 있다. 이때 아주 놀라운 사실을 깨닫았는데, 옷장 크기에 비해 옷걸이가 많을 경우 옷걸이에 옷걸이를 걸면 옷을 더 많이 걸 수 있다는 사실이다 !!!

옷걸이에 옷을 거는 대신 양쪽에 옷걸이를 걸면 옷을 더 걸 수 있는데, 옷걸이의 균형을 위해 옷걸이의 양쪽에 걸리는 옷걸이의 총 개수가 같은 완전 이진 옷걸이를 만들어야 한다. 이때 당연히 옷걸이가 걸리지 않은 맨 아래 옷걸이에만 옷을 걸 수 있다.

옷걸이 하나를 높이가 1인 옷걸이 트리라 할 때, 옷걸이 양쪽에 옷걸이 두 개를 걸면 높이 2인 옷걸이 트리가 된다. 이를 반복하여 옷걸이 양쪽에 높이 $i$인 옷걸이 트리를 걸면 높이 $i+1$인 옷걸이 트리가 된다. 옷장의 높이가 낮아 높이 3 이하인 옷걸이 트리에만 옷을 걸 수 있다. 높이가 4인 옷걸이 트리는 옷장에 넣을 수 있지만 높이 때문에 밑에 옷을 걸 수 없고, 높이가 5 이상인 옷걸이 트리는 옷장에 넣을 수 없다. 옷걸이를 둘 다른 장소가 없어 옷걸이를 남김없이 사용해야 하며, 모든 옷걸이를 걸 수 있는 위치에 옷걸이 트리를 배치할 필요는 없다.

조건을 만족하며 옷걸이 트리를 배치할 때 걸 수 있는 옷의 최대 수를 구하시오.

## 입력

첫 번째 줄에 옷걸이를 걸 수 있는 위치의 개수와 옷걸이의 수 $N, M$가 주어진다. ($1\leq N \leq5,000, 1\leq M \leq 10,000$)

## 출력

첫 번째 줄에 최대로 걸 수 있는 옷의 개수를 출력한다. 만약 위의 조건을 만족하며 $M$개의 옷걸이를 $N$개 이하의 위치에 걸 방법이 없다면 $-1$을 출력한다.

## 풀이
#### 4NM 냅색으로 해결하였다.

``` c++
#include<bits/stdc++.h>
using namespace std;

const int MAX = 10'016;

int maxScore[MAX];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;

memset(maxScore, -1, sizeof maxScore);
    maxScore[0]=0;

for(int i=0;i<n;i++) {
 for(int j=m;j>=0;j--) {
 if(maxScore[j]!=-1) {
 maxScore[j+1] = max(maxScore[j+1], maxScore[j]+1);
 maxScore[j+3] = max(maxScore[j+3], maxScore[j]+2);
 maxScore[j+7] = max(maxScore[j+7], maxScore[j]+4);
 maxScore[j+15] = max(maxScore[j+15], maxScore[j]);
 }
 }
 }
 cout << maxScore[m];
}
```