[백준]BOJ #33918: 맛있는 스콘 만들기

작성일 | In

링크: https://www.acmicpc.net/problem/33918

풀이

  • 시각 t에 완성되는 스콘 맛의 최댓값은 시각 t-1의 값에 의존
  • dp[t][k] : 시각 t, 온도 k일 때 스콘 맛의 최댓값이라 하자
  • r = D/C 라고 가정했을 때, 아래 수식을 도출할 수 있음


\[dp[t][k] = \max_{P = -r}^{r} \left( dp[t-1][k + P \cdot C] + \left( M - |b_k - k| \right) \right)\]


\[dp[t][k] = \left( \max_{P = -r}^{r} dp[t-1][k + P \cdot C] \right) + \left( M - |b_k - k| \right)\]

시도 1

  • 시각 0부터 N-1 까지 bottom-up으로 최댓값을 구하는 방식으로 시도
  • 시간 복잡도 = O( N*M*r)
  • D = M, C = 1 일 때, r = D/C = M 이므로 O(NM^2), 시간 초과

    시도 2

  • 각 시각과 온도에서 최적의 값을 구하기 위해서 N*M의 순회는 반드시 필요하다고 생각
  • 우선순위 큐를 통해 O(1)로 각 단계의 최댓값을 얻도록 함
  • r 만큼 건너뛰면서 확인을 하는 것이 번거롭다


33918-1


r만큼 건너뛰면서 확인을 해야 하기 때문에 r로 나누었을 때 나머지가 동일한 값끼리 우선순위 큐에 넣어서 확인하면 되겠다.

위 예제를 통해 보면, 색깔이 같은 것끼리 우선순위 큐에 넣고 범위만 확인하면 된다.

1
2
3
4
5
6
7
8
9
10
11
시각 t       -> 시각 t+1
-------------------------
1 3 5       -> 1
1 3 5 7     -> 3
1 3 5 7     -> 5
3 5 7       -> 7

2 4 6       -> 2
2 4 6 8     -> 4
2 4 6 8     -> 6
4 6 8       -> 8

33918-2


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
int C, D;
int b[TIME_MAX];
int dp[TIME_MAX][TEMP_MAX];

void init()
{
    cin >> N >> M >> C >> D;
    fozi(N)
    {
        cin >> b[i];
    }
}

void solution()
{
    memset(dp, 0, sizeof(dp));
    priority_queue<pii> pq;

    for (int time = 0; time < N; ++time)
    {
        for (int temp = 1; temp <= M; ++temp)
        {
            dp[time][temp] = M - abs(b[time] - temp);
        }
    }

    for (int time = 0; time < N; ++time)
    {
        for (int pivot = 1; pivot <= C; ++pivot)
        {
            while (!pq.empty())
                pq.pop();

            int mid = pivot;
            for (mid = pivot; mid <= pivot + D && mid <= M; mid += C)
            {
                pq.push({dp[time][mid], mid});
            }

            for (mid = pivot; mid <= M; mid += C)
            {
                if (mid != pivot && mid + D <= M)
                {
                    pq.push({dp[time][mid + D], mid + D});
                }
                while (!pq.empty() && pq.top().second < mid - D)
                {
                    pq.pop();
                }

                dp[time + 1][mid] += pq.top().first;
            }
        }
    }

    int answer = 0;
    for (int temp = 1; temp <= M; ++temp)
        answer = max(answer, dp[N - 1][temp]);

    cout << answer;
}

int main()
{
    ios_base::sync_with_stdio(false); // disable synchronization C, C++ I/O
    cin.tie(NULL);                    // untie cin from cout

#ifdef ENABLE_TESTCASE
    cin >> T;
    while (T--)
    {
#endif
        init();
        solution();
#ifdef ENABLE_TESTCASE
    }
#endif
}

Reference