콘서트(CONCERT) 정답 코드

난이도 ★★★☆☆

문제를 보시려면 여기를 클릭

틀리기 쉬운 입출력 예제

입력	출력
3 1 5 9 5 1 5 9 6 50 1 24 1 2 2 2 4 2 3 2 1 2 3 2 1 2 3 2 3 2 1 2 3 1 2 3 2 5 3 5 3 2 2 5 6 6 7 7 5 8 7 8 7 5 7 5 6 5 6 6 6 4	0 -1 24

힌트

동적계획법의 전형적인 문제이지만 문제 이해가 좀 어렵다.  → 이해했다면 동적계획법의 틀(재귀함수 + 캐시)대로 구현하면 된다.

이하는 코드입니다.

#include <stdio.h>
#include <string.h>
 
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
 
#define FAIL -3
#define N_MAX 50
#define VM_MAX 1000
 
#pragma warning(disable:4996)
 
int N, VM;
int board[N_MAX];
int cache[N_MAX + 2][VM_MAX];
 
int getMaxVolume(int VS, int boardIndex) {
    if ((VS < 0) || (VS > VM)) {
        return FAIL;
    }
 
    int& ret = cache[boardIndex][VS];
    if (ret != -1) {
        return ret;
    }
 
    if (boardIndex == N) {
        return ret = VS;
    }
 
    return ret = (MAX(getMaxVolume(VS + board[boardIndex], boardIndex + 1), getMaxVolume(VS - board[boardIndex], boardIndex + 1)));
}
 
int main() {
    int T;
    scanf("%d\n", &T);
 
    while (T-- > 0) {
        // get N, VS, VM
        int VS;
        scanf("%d %d %d", &N, &VS, &VM);
 
        // get Vi
        for (int i = 0; i < N; i++) {
            scanf("%d", &board[i]);
        }
 
        // solve and print
        memset(cache, -1, sizeof(cache));
        int maxVolume = getMaxVolume(VS, 0);
        if (maxVolume == FAIL) {
            maxVolume = -1;
        }
        printf("%d\n", maxVolume);
    }
 
    return 0;
}