[C++] SWEA 1486 - 장훈이의 높은 선반

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b7Yf6ABcBBASw&categoryId=AV2b7Yf6ABcBBASw&categoryType=CODE

SW Expert Academy

<풀이>

1. 선반 높이와 점원들의 키를 입력받는다.

2. 점원들의 키를 사용하여 얻을 수 있는 선반 높이 중, 선반 높이보다 크면서 가장 가까운 값을 출력한다.

 

<해법>

1. 점원들이 만들 수 있는 탑 높이를 계산하는 방법

=> 모든 경우를 다 해보아야합니다. 각각의 점원을 사용할지 안할지를 정하고, 모든 점원의 사용여부가 결정되었을때 결과를 갱신합니다.

저는 위 그림과 같은 상태공간트리가 그려지도록 구현하였습니다.

 

#include <iostream>
#include <string.h>
#include <algorithm>
#define INF 987654321
 
using namespace std;
 
int N, B;
int H[20];
int answer;
 
void makeTower(int index, int sumHeight) {
 
    //종료조건
    if (index == N) {
        if (sumHeight >= B) {
            //결과 갱신
            answer = min(answer, sumHeight);
        }
        return;
    }
 
    //현재 탑을 쌓는 경우 해보기
    makeTower(index + 1, sumHeight + H[index]);
 
    //현재 탑을 쌓지 않는 경우 해보기
    makeTower(index + 1, sumHeight);
}
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        N = 0, B = 0;
        memset(H, 0, sizeof(H));
        answer = INF;
 
        //입력
        cin >> N >> B;
        for (int i = 0; i < N; i++) {
            cin >> H[i];
        }
 
        //해법
        makeTower(0, 0);
 
        //출력
        cout << "#" << test_case << " " << answer - B << "\n";
    }
 
    //종료
    return 0;
}

 

브루트포스에 대해 알아볼 수 있는 문제였습니다.