[백준/C++] 25706번: 자전거 묘기

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

• 문제 코드

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int N = 0;
    cin >> N;
    vector<int> v1;
    vector<int> ans(N);
    int num = 0;
    for (int i = 0; i < N; i++) {
        cin >> num;
        v1.push_back(num);
    }
    for (int i = N-1; i >=0; i--) {
        if (i == N - 1) {
            ans[i] = 1;
        }
        else {
            if (v1[i] == 0) {
                ans[i] = ans[i + 1] + 1;
            }
            else {
                if (i + v1[i] + 1 >= N) {
                    ans[i] = 1;
                }
                else {
                    ans[i] = ans[i + v1[i] + 1] + 1;
                }
            }
        }
    }
    for (int i = 0; i < N-1; i++) {
        cout << ans[i] << " ";
    }
    cout << ans[N - 1] << endl;
}

• 문제 풀이

기존에 쓰던 배열을 사용하면 메모리 낭비가 너무 심할 것 같아서 벡터를 사용했다. 문제에서 알려준 규칙대로 반복문을 사용해 N번째 수부터 탐색하여 밟은 도로를 누적하였다. N번쨰 수이거나 인덱스 값이 넘어가면 무조건 1으로 초기화하는 것만 예외처리 해주면 되었다.