문제은행 롤러코스터 & BOJ 6208 Cow Roller Coaster(C++)

1546 : 롤러코스터

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 3 회    시도횟수: 3 회   

소들이 롤러코스터를 만들고자 한다! 그들을 도와 가장 재미있는 롤러코스터를 설계해 보자.

 

롤러코스터의 가로 길이는 L(1≤L≤1,000)로 주어진다. 롤러코스터는 각 구간을 부품처럼 조립하여 만든다. 우리가 사용할 수 있는 구간은 총 N(1≤N≤10,000)개로 주어진다. 각 부품이 놓일 수 있는 가로 위치는 Xi로 정해져 있다. 또한 구간의 가로길이도 Wi로 주어져 있다. 또한 그 구간을 사용할 경우 드는 비용 Ci(1≤Ci≤1,000)와 재미있는 정도 Fi(1≤Fi≤1,000,000)도 주어져 있다.

 

소들은 롤러코스터를 만들기 위해 B(1≤B≤1,000)만큼의 예산을 마련해 놓았다. 구간들의 비용의 합이 예산을 넘지 않으면서 가장 재미도의 합이 가장 큰 롤러코스터를 설계해야한다. 물론 롤러코스터가 끊겨서는 안 된다.

 

L, N, B가 입력된다.
다음 N줄에 걸쳐 각 구간의 Xi, Wi, Fi, Ci가 주어진다.

최대 재미도의 합을 출력한다. 만약 조건에 맞추어 설계가 불가능하다면 -1을 출력한다.

[Copy] 5 6 10 0 2 20 6 2 3 5 6 0 1 2 1 1 1 1 3 1 2 5 4 3 2 10 2

[Copy] 17

출처 : USACO 2006 December Silver

https://www.acmicpc.net/problem/6208

정올과 백준온라인저지 문제가 동일. 

?

 
/**************************************************************
    Problem: 1546
    User: a132034
    Language: C++
    Result: Success
    Time:32 ms
    Memory:50448 kb
****************************************************************/
 
 
#include    <stdio.h>
#include    <vector>
#include    <algorithm>
#include    <functional>
#include    <iostream>
#pragma warning(disable : 4996)
 
static int sum = -1; //결과 출력
struct PARTS
{
    int x;
    int w;
    int f;
    int c;
    int e; //끝나는 지점(x+w)
 
    PARTS(int x_, int w_, int f_, int c_){ x = x_; w = w_; f = f_; c = c_; e = x_ + w_; }
}; //부품 (시작점, 길이, 재미지수, 가격)
static int FUN[11111][1111]; //재미지수 (길이까지, 남은 버짓)
static std::vector<PARTS> v;
template<template <typename> class P = std::less >
struct compare {
    bool operator()(const PARTS& a, const PARTS& b) {
        return P<int>()(a.x, b.x);
    }
};
int main()
{
    int L, N, B;
    int x, w, f, c;
    scanf("%d %d %d", &L, &N, &B);
     
    for (int i = 1; i <= N; ++i)
    {
        scanf("%d %d %d %d", &x, &w, &f, &c);
        v.push_back(PARTS(x, w, f, c));
    }
    sort(v.begin(), v.end(), compare<std::less>());
 
    for (int i = 1; i <= N; ++i)
    {
        if (v.front().x == 0) //시작점
        {
            FUN[v.front().w][B - v.front().c] = v.front().f;
            v.erase(v.begin());
        }
    }
    for (std::vector<PARTS>::iterator it = v.begin(); it != v.end(); ++it)
    {
        for (int b = 0; b <= B; ++b)
        {
            if (FUN[it->x][b] == 0)
                continue;
            else
            {
                //버짓 내에 된다면
                if (b - it->c >= 0)
                {
                    FUN[it->e][b - it->c] = std::max(it->f + FUN[it->x][b], FUN[it->e][b - it->c]);
                }
            }
        }
    }
    int max = 0;
    for (int i = 0; i <= B; ++i)
    {
        if (FUN[L][i] > max)
            max = FUN[L][i];
    }
    if (max == 0)
        printf("-1\n");
    else
        printf("%d\n", max);
 
    return 0;
}
 

다이나믹 프로그래밍으로 풀었다. (아마 맞을것..)

냅색문제 비슷한 느낌으로 생각을 해서 

FUN 배열을 만들었다. 이 배열은 길이 L까지 왔을 때 최대의 재미요소를 저장하기 위해 만들었고, Budget을 초과하면 안되므로 Budget에 대해서도 신경쓰려다 보니 FUN[길이][예산] 의 배열이 나오게 되었다. 

기존 입력받은 부품 정보들은 x(시작점), w(길이), f(재미요소), c(가격) 인데 추가로 x+w(끝나는 지점) 을 저장하기 위해 e변수를 넣었다. 

우리가 구할 것은 FUN[L] - L까지 왔을 때 FUN중 가장 큰 수 (예산이 얼마가 남는지는 상관없음) 이었으므로 

74~84라인까지 FUN[L][0]부터 FUN[L][B]까지 중 가장 큰 수를 뽑아내는 작업을 하였고

가장 핵심적인 부분은 

부품정보를 입력받은 후 부터 시작하는 점(x)를 기준으로 시작점이 빠른 것 부터 정렬해 주었다. 

이는 다음 부품을 사용하기 전에 더 먼저 시작한 부품을 확인해주기 위함이다. (아래 표로 확인하는 것이 더 편할 것 같다..)

입력받은 예제를 기준으로 정렬하게 되면 

5 6 10 -> L N B

입력

0 2 20 6

2 3 5 6

0 1 2 1

1 1 1 3

1 2 5 4

3 2 10 2

정렬 후

0 2 20 6

0 1 2 1

1 1 1 3

1 2 5 4

2 3 5 6

3 2 10 2

이제 하나씩 FUN 배열에 넣어주게 된다. 

첫 번째 부품부터 넣게 된다. 첫 번째 부품을 넣을 경우 이전의 부품이 없으므로 이전에 값이 없을 것이라 생각해서 비교하지는 않았다. 

 0 2 20 6 삽입 - 2까지 왔을 때 예산을 6 썻으므로 4가 남는다. 재미요소는 20

	B	0	1	2	3	4	5	6	7	8	9	10
L	0
	1
	2					20
	3
	4
	5

0 1 2 1 삽입 - 1까지 왔을 때 예산을 1 사용. 9의 예산이 남고 재미요소는 2

	B	0	1	2	3	4	5	6	7	8	9	10
L	0
	1										2
	2					20
	3
	4
	5

1 1 1 3 삽입 - 출발지점이 1이므로 FUN[1][0~Budget]을 살펴본다. 있는 것 중 이 부품을 사용해도 예산초과가 나지 않는 경우 기존의 있는 길이, 예산의 재미요소와 비교했을 때 더 크면 삽입. (이 경우에는 FUN[2][6]에 들어가야 하나 기존 재미요소가 없으므로 그대로 삽입)

	B	0	1	2	3	4	5	6	7	8	9	10
L	0
	1										2
	2					20		3
	3
	4
	5

1 2 5 4 삽입 - 1에서 시작하기 위해 찾아봄. 9의 예산을 남기고 길이 1인 부품조합을 찾음. 예산 5 남고 총 7의 재미요소를 가짐(2+4)

	B	0	1	2	3	4	5	6	7	8	9	10
L	0
	1										2
	2					20		3
	3						7
	4
	5

2 3 5 6 삽입 - 2에서 시작하는 것 중 20의 재미요소를 가진 부품은 이미 예산이 4뿐이라 안됨. 3의 재미요소를 가진 부품은 6이라 가능. 총 재미요소 8

	B	0	1	2	3	4	5	6	7	8	9	10
L	0
	1										2
	2					20		3
	3						7
	4
	5		8

3 2 10 2 삽입 - 3에서 시작하는 부품조합은 예산이 5 남은 부품조합이 있어서 가능. 총 재미요소 17 

	B	0	1	2	3	4	5	6	7	8	9	10
L	0
	1										2
	2					20		3
	3						7
	4
	5		8		17

길이 5일 때의 재미요소 배열 중 가장 큰 재미요소를 가지는 조합은 FUN[5][3] => 17이 된다. 

처음 시작점이 0인 부품을 먼저 입력받은 이유는 단순히 코딩을 편하게 하려는 이유였다. 한 루틴안에 전부 넣을 수도 있을 것 같다.