BOJ 20984 Growing Vegetables is Fun 4

Problems

문제 링크:

문제 내용

양의 정수로 이루어진 길이 $N$ 의 배열 $A$ 가 주어집니다. 당신은 다음의 동작을 사용하여 이 배열을 바이토닉 배열로 만들어야 합니다.

두 인덱스 $1 \le L, R \le N$ 을 골라서, $A_L, A_{L+1}, \cdots, A_{R-1}, A_{R}$ 에 1을 더합니다.

바이토닉 배열의 정의는 다음과 같습니다.

어떤 인덱스 $1 \le k \le N$ 가 존재하여, 모든 $1 \le j < k$ 에 대해 $A_j < A_{j+1}$ 이고, 모든 $k < j \le N$ 에 대해 $A_{j-1} > A_j$ 입니다. 즉, 인덱스 $k$ 를 기준으로 $k$ 번째를 포함한 왼쪽은 strictly 증가하고, 오른쪽은 strictly 감소합니다.

이를 달성하기 위해 필요한 동작의 최소 횟수를 구하세요.

입력

첫 줄에는 배열의 길이 $N$ 이 주어집니다.

다음 줄에는 배열의 각 원소가 주어집니다. 이 값들은 $10^9$ 를 초과하지 않습니다.

문제 풀이

스포일러

바이토닉 수열로 만들기 위해 증가시켜야 하는 값들이 “약한 바이토닉”(바이토닉이지만 이웃한 값이 서로 같은 것도 허용)을 이룬다면, 필요한 동작의 횟수는 그들 중 가장 큰 값과 같습니다.

그렇지 않은 경우에는 따로따로 1을 더해줘야 하는 서로 disjoint한 두 구간이 존재하게 됩니다. 그 사이의 “골짜기"를 메워서 두 구간을 동시에 더해주게 되면 이웃한 두 값이 같아져 바이토닉이 깨질 수 있는데, 이 경우 그러한 경계 안쪽으로 1을 추가로 더하여 다시 바이토닉으로 만들어 줄 수 있습니다. 따라서 바이토닉을 만드는 모든 방법은 적어도 그것과 동등하게 좋은 “약한 바이토닉"한 방법이 존재합니다.

이를 이용하여, 다음과 같이 계산하여 답을 구할 수 있습니다.

각 인덱스를 왼쪽부터 확인하여, 현재 인덱스까지가 strictly 증가하게 하기 위해 더해줘야 하는 횟수 $l[i]$ 를 구합니다. 현재 값이 이전 값보다 크면 $l[i]$ 는 $l[i-1]$ 과 같고, 작거나 같다면 $l[i-1]$ 에 두 원소의 차이 + 1을 더해 줍니다.
같은 방법으로 오른쪽에서 왼쪽 방향에 해당하는 값 $r[i]$ 도 구합니다.
이제 모든 인덱스 $i$ 에 대해서 $\max(l[i], r[i])$ 의 최솟값을 출력하면 됩니다.

Last updated on 2025년 10월 1일 16:02:24

BOJ 20953 고고학자 예린 BOJ 21042 Triangle of Safety