BOJ 8548 Tarasy
문제 내용
이하의 양의 정수로 이루어진 길이 의 수열이 주어집니다. () 당신은 수열에서 원하는 시작점을 골라서 방문하고, 그 다음부터 좌우로 인접한 원소로 이동할 수 있습니다.
작은 원소에서 큰 원소로 이동하는 데에는 그 차이만큼의 비용이 들고, 큰 원소에서 작은 원소(또는 같은 원소)로 이동하는 데에는 비용이 들지 않습니다.
비용의 상한 ()가 주어질 때 방문할 수 있는 원소의 수의 최댓값을 구하세요.
입력
첫 줄에 과 가 주어집니다. 다음 줄에 걸쳐 수열의 원소의 값이 하나씩 순서대로 주어집니다.
문제 풀이
스포일러
먼저, 같은 쌍의 원소 사이를 두 번 이상 이동하는 것은 절대로 이득이 되지 않습니다. 이렇게 이동하려면 적어도 한 번은 오른쪽으로, 한 번은 왼쪽으로 이동해야 하는데, 그러면 두 수의 차이만큼의 비용을 반드시 지불하게 되기 때문입니다.
따라서 오른쪽으로만 이동하는 것과 왼쪽으로만 이동하는 것만 고려하면 됩니다.
이 작으므로 한쪽 방향으로 이동할 때의 비용의 누적합을 구한 후 개의 구간을 브루트포스하여 비용이 이내인 것 중 가장 긴 것을 찾는 풀이가 통과합니다. 이를 시간에 구하려면 투 포인터를 하여 오른쪽으로 연장하다가 비용이 초과되면 왼쪽을 축소하는 방법을 사용할 수 있습니다.