[백준] 30464번 : 시간낭비 (C++)

30464번 : 시간낭비

---

문제)

건덕이는 학교에 가기 너무 싫은 나머지 최대한 늦게 학교에 도착하려고 한다. 등굣길은 N개의 칸이 가로로 놓인 형태이며, 각 칸은 가장 왼쪽 칸부터 오른쪽으로 1부터 N까지 번호가 매겨진다. 건덕이는 1번 칸에, 학교는 N번 칸에 존재한다.

 

건덕이는 처음에 학교를 바라보는 방향으로 서 있다. 등교하는 방법은 특이한데, 1분마다 현재 자신이 서 있는 칸에 쓰인 수만큼 바라보는 방향으로 이동한다. 이때, 등굣길을 벗어나도록 이동할 수 없다.

 

건덕이는 바라보는 방향을 최대 두 번 반전할 수 있다. 학교가 있는 칸에 처음으로 도착하는 시간을 최대한 늦추면 출발 몇 분 뒤에 도착할까? 건덕이가 방향을 반전하는 데 드는 시간은 무시한다.

 

 

 

입력 :

첫 번째 줄에 학교가 있는 칸의 번호 N이 주어진다. ( 3 ≤ N ≤ 200000 ) 

두 번째 줄에 각 칸에 쓰인 정수 a_i가 공백으로 구분되어 주어진다. (0≤ a_i ≤200 000)

 

 

 

출력 :

건덕이가 최대한 시간을 끈 뒤, 학교가 있는 칸에 처음으로 도착하는 시간을 출력한다. 학교에 도착할 수 있는 경로가 없다면 −1을 출력한다.

 

 

 

 

 

 

 

풀이)

// 30464. 시간낭비
#include <iostream>
 
using namespace std;
 
int n;
int vec[200001];
int dp[200001][2][2];
 
int recur(int cur, int dir, int cnt)
{
    // 등교길을 벗어났을 경우
    if (cur < 0 || cur >= n) return -99999999;
 
    // 학교에 도착했을 경우
    if (cur == n - 1) return 0;
 
    // 함정?에 걸려 움직이지 못할 경우
    if (vec[cur] == 0) return -99999999;
 
    if (dp[cur][dir][cnt] != -1) return dp[cur][dir][cnt];
 
    int ret = -9999999;
 
    if (cnt > 0)
    {
        // 방향을 꺾는 판단
        {
            // 오른쪽으로 가고 있었을 경우
            if (dir == 0) ret = max(ret, recur(cur - vec[cur], !dir, cnt - 1) + 1);
        
            // 왼쪽으로 가고 있었을 경우
            else if (dir == 1) ret = max(ret, recur(cur + vec[cur], !dir, cnt - 1) + 1);
        }
        
        // 방향을 바꾸지 않는 판단
        {
            if (dir == 0) ret = max(ret, recur(cur + vec[cur], dir, cnt) + 1);
            else if (dir == 1) ret = max(ret, recur(cur - vec[cur], dir, cnt) + 1);
        }
    }
    // 방향 전환을 모두 사용했을 경우
    else if (cnt == 0)
    {
        // 현재 방향에 맞춰서 무조건 간다.
        if (dir == 0) ret = max(ret, recur(cur + vec[cur], dir, cnt) + 1);
        else if (dir == 1) ret = max(ret, recur(cur - vec[cur], dir, cnt) + 1);
    }
 
    dp[cur][dir][cnt] = ret;
 
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++) cin >> vec[i];
    fill(&dp[0][0][0], &dp[200000][1][2], -1);
 
    int ans = recur(0, 0, 2);
 
    if (ans <= 0) cout << -1;
    else cout << ans;
 
    return 0;
}

---

출처 : https://www.acmicpc.net/problem/30464 

30464번: 시간낭비