백준 27953 - 공룡 게임 (C++)

문제

• 문제 링크

  
   BOJ 27953 - 공룡 게임 
  

• 문제 요약

$N$개의 장애물을 $2$가지 행동을 이용해 넘어야 한다.
각 행동마다 그에 따른 패널티를 받을 때, 모든 장애물을 넘기 위한 최소 패널티를 구해보자.

• 제한

TL : $1$ sec, ML : $1024$ MB




$1 ≤ N ≤ 5,000$

$1 ≤ A, B, X, Y, T_i ≤ 10^9$

$S_i ∈ {1, 2, 3}$

$T_i < T_j$

알고리즘 분류

• 다이나믹 프로그래밍(dp)

풀이

만약 이 문제 의 향기를 맡았다면 정답이다.

$dp[p][q]$ : 마지막으로 점프, 슬라이딩을 한 장애물이 각각 $p, q$ 일 때 남은 장애물들을 넘기 위한 최소 패널티.

구체적으로,
임의의 장애물 $k$를 점프로 극복 하려면

• $S[k]$ 가 홀수이고
• $T[k] - T[p] >= A$ 일 때
• $dp[k][q] + X$ 의 패널티로 극복 할 수 있다.

임의의 장애물 $k$를 슬라이딩으로 극복 하려면

• $S[k]$ 가 $1$보다 크고
• $T[k] - T[q] >= B$ 일 때
• $dp[p][k] + Y$ 의 패널티로 극복 할 수 있다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
 
int n, A, B, X, Y, T[5001]{ -(int)1e9 }, S[5001];
ll dp[5001][5001];
 
ll f(int p, int q)
{
    ll& t(dp[p][q]), k(max(p, q));
    if (k++ == n) return 0;
    if (!~t)
    {
        t = 1e18;
        if (S[k] & 1 && T[k] - T[p] >= A) t = min(t, f(k, q) + X);
        if (S[k] > 1 && T[k] - T[q] >= B) t = min(t, f(p, k) + Y);
    }
    return t;
}
int main()
{
    memset(dp, -1, sizeof dp);
    cin >> n >> A >> B >> X >> Y;
    for (int i(1); i <= n; i++) scanf("%d %d", &T[i], &S[i]);
    cout << (f(0, 0) < 1e18 ? f(0, 0) : -1);
}

comment

끝