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

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

풀이

N이 최대 20이므로 완전탐색으로 해결할 수 있다. 탐색을 하면서 값을 갱신하여 가지치기를 하여 최적화했다.

코드

#include <iostream>
#include <algorithm>
using namespace std;

int n, b, ans;
int h[20];

void dfs(int idx, int sum) {
    // 탐색 중에 나온 합계가 기존에 구한 값보다 크면 종료
    if (sum > ans) return;
    if (sum >= b) {
        ans = min(ans, sum);
        return;
    }
    for (int i = idx + 1; i < n; i++)
        dfs(i, sum + h[i]);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    for (int c = 1; c <= t; c++) {
        ans = 987654321;
        cin >> n >> b;
        for (int i = 0; i < n; i++)
            cin >> h[i];
        dfs(-1, 0);
        cout << "#" << c << ' ' << ans - b << '\n';
    }
    return 0;
}