백준 30464 - 시간낭비 (C++)

문제

• 문제 링크

  
   BOJ 30464 - 시간낭비 
  

• 문제 요약

$a_1, a_2, ... , a_N$이 주어진다.
각 $a_i$에서는 해당 칸에 적힌 칸만큼 바라보는 방향으로 이동할 수 있다.

바라보는 방향을 최대 두 번 반전할 수 있을 때, $a_1$에서 $a_N$에 최대한 늦게 도착하는 경우를 찾아보자.


• 제한

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




$3 ≤ N ≤ 200,000$

$0 ≤ a_i ≤ 200,000$

알고리즘 분류

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

풀이

어떤 위치에서 고려해야할 상태는 $3$가지가 있다고 생각했다.

어느 위치$?$

어느 방향$?$

지금까지 몇 번 반전$?$

이에 따라, 다음과 같이 점화식을 정의하자.

$dp[u][p][q] :$ $a_u$에서, 방향 $p$를 바라보고 있고 지금까지 $q$번 반전했을 때의 답. (단, $p = 0$이 오른 쪽)

그럼 상태 전이로 두 가지가 일어날 수 있다.

방향 $p$로 $a_u$만큼 이동한다.

방향을 반전시킨 후, $a_u$만큼 이동한다. 단, 반드시 $q < 2$이어야 한다.

마지막으로, $a_i = 0$인 경우를 주의하자.
나는 어떤 상태의 답을 계산할 때 우선 $inf$로 초기화하여 무한 루프가 발생하는 것을 막아 주었다.

전체 코드

#include<bits/stdc++.h>
#define N 200001
using namespace std;
 
int n, a[N], dp[N][2][3];
int f(int u, int p, int q)
{
    if (u < 1 || u > n) return -1e9;
    if (u == n) return 0;
    int& t(dp[u][p][q]);
    if (!~t)
    {
        t = -1e9;
        int dis(a[u] * (p ? -1 : 1));
 
        t = f(u + dis, p, q) + 1;
        if (q < 2)
            t = max(t, f(u - dis, p ^ 1, q + 1) + 1);
    }
    return t;
}
int main()
{
    cin >> n;
    for (int i(1); i <= n; scanf("%d", &a[i++]));
 
    memset(dp, -1, sizeof dp);
    int ans(f(1, 0, 0));
    cout << (ans > 0 ? ans : -1);
}

comment

끝