[BOJ 27542 // C++] 絶対階差数列 (Sequence of Absolute Differences)

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 27542번 문제인 絶対階差数列 (Sequence of Absolute Differences)이다.
문제는 아래 링크를 확인하자.

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

27542번: 絶対階差数列 (Sequence of Absolute Differences)

문제에서 주어진 대로 어떤 수열의 계차수열을 구해나갈 때마다 전체 수열의 길이는 1씩 줄어든다.

 

길이가 N인 수열을 입력받아, 길이가 N인 수열로부터 길이가 N-1인 수열을, 길이가 N-1인 수열로부터 길이가 N-2인 수열을, ..., 길이가 3인 수열로부터 길이가 2인 수열을, 길이가 2인 수열로부터 길이가 1인 수열을 얻는 것을 반복하는 것으로 문제를 해결하자. 이는 반복문을 이용해 구현할 수 있다.

 

길이가 N인 수열의 i번째 값과 i+1번째 값을 이용하여 길이가 N-1인 수열의 i번째 값을 얻을 때 새로운 수열의 값을 앞에서부터 계산해 얻어나간다면 더 이상 길이가 N인 수열의 i번째 값은 사용하지 않음을 확인하자. 이를 이용하면 2차원 배열의 선언 없이 1차원 배열만으로 아래와 같이 기존 수열의 값을 덮어쓰면서 계산하는 구현이 가능하다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N;
int arr[2000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) cin >> arr[i];

	for (int k = N - 1; k > 0; k--) {
		for (int i = 0; i < k; i++) arr[i] = abs(arr[i + 1] - arr[i]);
	}

	cout << arr[0];
}