다이나믹 롤러 17393

문제

접근 방법

길이를 저장하여 넘어가는 방식을 사용하여 풀 수 있다.
이전의 길이를 이용하여 풀기에 다이나믹 프로그래밍이라 할 수 있지 않을까 싶었다.

코드

#include <iostream>
#include <vector>
using namespace std;
typedef unsigned long long ull;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int N;
    cin >> N;
    vector<ull> A(N), B(N);
    vector<int> ret(N);
    for (int i = 0; i < N; ++i)
        cin >> A[i];
    for (int i = 0; i < N; ++i)
        cin >> B[i];
    for (int i = N - 2; i >= 0; --i)
    {
        int cnt = 0;
        for (int j = i + 1; j < N; ++j)
        {
            if (A[i] < B[j]) // 점도 지수는 오름차순이기에 뒤엣것을 더 볼 필요 없다.
                break;
            if (A[i] >= A[j] && ret[j]) // 잉크 지수가 같거나 크다면 넘어갈 수 있다.
            {
                cnt += ret[j];
                j += ret[j] - 1;
                continue;
            }
            ++cnt;
        }
        ret[i] = cnt;
    }
    for (int i : ret)
        cout << i << " ";
    return 0;
}

풀이

알고 보니 이분 탐색을 활용하는 문제였다. 확실히 오름차순이기에 점도 지수가 이하인 칸을 찾으면 해결되는 것이다.

설명을 보고 놀랐다.
아무리 봐도 스플래툰 설정을 활용한 문제이기 때문이다.

다이나믹 롤러->다이나모 롤러
멩미->만멘미
잉크칠, 부키치

반가운 느낌이 들었다.