양의 정수로 이루어진 목표 배열 arr[]가 주어졌을 때, 모든 요소가 0으로 초기화된 배열에서 출발하여 이 목표 배열을 만들어야 합니다. 이때 사용할 수 있는 연산은 접미사(suffix) 증가/감소 연산입니다.
연산의 정의
접미사 증가 연산: 임의의 인덱스 i를 선택하면, 인덱스 i부터 배열의 마지막 인덱스까지 모든 요소에 1을 더합니다.
접미사 감소 연산: 임의의 인덱스 i를 선택하면, 인덱스 i부터 배열의 마지막 인덱스까지 모든 요소에서 1을 뺍니다.
예제로 이해하기
예제 1
입력: arr[] = { 1, 2, 3 }
출력: 주어진 배열을 구성하기 위한 접미사 증가/감소 연산 횟수 = 3
설명:
{ 0, 0, 0 } 에서 시작
인덱스 0 선택 → 접미사 증가 적용 → { 1, 1, 1 }
인덱스 1 선택 → 접미사 증가 적용 → { 1, 2, 2 }
인덱스 2 선택 → 접미사 증가 적용 → { 1, 2, 3 }
총 연산 횟수 = 3예제 2
입력: arr[] = { 1, 4, 5, 3 }
출력: 주어진 배열을 구성하기 위한 접미사 증가/감소 연산 횟수 = 7
설명:
{ 0, 0, 0, 0 } 에서 시작
인덱스 0 선택 → 접미사 증가 적용 → { 1, 1, 1, 1 }
인덱스 1 선택 → 접미사 증가 적용 → { 1, 2, 2, 2 }
인덱스 1 선택 → 접미사 증가 적용 → { 1, 3, 3, 3 }
인덱스 1 선택 → 접미사 증가 적용 → { 1, 4, 4, 4 }
인덱스 2 선택 → 접미사 증가 적용 → { 1, 4, 5, 5 }
인덱스 3 선택 → 접미사 감소 적용 → { 1, 4, 5, 4 }
인덱스 3 선택 → 접미사 감소 적용 → { 1, 4, 5, 3 }
총 연산 횟수 = 7접근 방법
초기 배열을 B[]라고 가정해 보겠습니다.
- 첫 번째 요소 B[0]을 arr[0]과 같게 만들려면 arr[0]번의 접미사 증가 연산이 필요합니다. 이 시점 이후에는 B[0] = B[1] = ... = B[n-1] = arr[0]이 모두 같은 값을 갖습니다.
- 두 번째 요소 B[1]을 arr[1]과 같게 만들려면 |arr[1] − arr[0]|번의 연산(증가 또는 감소)이 추가로 필요합니다.
- 일반화하면, B[i]를 arr[i]와 같게 만들기 위해 필요한 연산 횟수는 |arr[i] − arr[i−1]|입니다.
따라서 총 연산 횟수는 다음과 같습니다.
총 연산 횟수 = |arr[0]| + |arr[1] − arr[0]| + ... + |arr[n−1] − arr[n−2]|
알고리즘 단계
- 목표 배열을 arr[]로 입력받습니다.
- incr_decr_op(int arr[], int size) 함수는 배열과 그 길이를 매개변수로 받아, 주어진 배열을 구성하는 데 필요한 접미사 증가/감소 연산 횟수를 반환합니다.
- count 변수를 0으로 초기화합니다.
- for 반복문으로 배열 arr[]를 순회합니다.
- 인덱스가 0이면 count에 arr[i] 값을 더합니다.
- 그 외의 인덱스에서는 count에 abs(arr[i] − arr[i−1]) 값을 더합니다.
- 반복문이 끝나면 count를 결과로 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int incr_decr_op(int arr[], int size){
int count = 0;
for (int i = 0; i < size; i++){
if (i > 0){
count += abs(arr[i] - arr[i - 1]);
}
else{
count = count + abs(arr[i]);
}
}
return count;
}
int main(){
int arr[] = { 3, 3, 1, 2, 2 };
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"주어진 배열을 구성하기 위한 접미사 증가/감소 연산 횟수: "<<incr_decr_op(arr, size) << endl;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
주어진 배열을 구성하기 위한 접미사 증가/감소 연산 횟수: 6
이처럼 인접한 두 요소 간의 차이의 절댓값을 누적하는 방식만으로 O(n) 시간 복잡도 안에 문제를 해결할 수 있습니다. 실제로 연산을 하나씩 시뮬레이션할 필요 없이, 수학적 관찰만으로 최소 연산 횟수를 바로 계산할 수 있다는 점이 이 문제의 핵심입니다.