[백준 1551] 수열의 변화

문제출처: https://www.acmicpc.net/problem/1551

문제

크기가 N인 수열 A가 주어졌을 때, 세준이는 인접한 두 원소의 차이를 이용해서 크기가 N-1인 수열 B를 만들 수 있다.

예를 들어, A = {5,6,3,9,-1} 이었을 때, B = {6-5, 3-6, 9-3, -1-9} = {1,-3,6,-10}이 된다. 다른 말로 B[i] = A[i+1]-A[i]가 된다.

수열 A가 주어졌을 때, 세준이가 위의 방법을 K번 했을 때 나오는 수열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 N과 K가 주어진다. N은 20보다 작거나 같은 자연수이고, K는 0보다 크거나 같고, N-1보다 작거나 같은 자연수이다. 둘째 줄에는 수열이 ‘,’로 구분되어 주어진다.

출력

첫째 줄에 K번 변형한 수열을 ‘,’로 구분하여 출력한다.

풀이

한 턴이 지날때 마다 저장된 값의 개수가 한개씩 줄어들어서 이 요소들을 어떻게 담을까 고민한문제입니다. 결국은 규칙만 찾아서 이중 반복문으로

해결 할 수 있었고 간단한 문제였습니다.

조건에 맞게 배열index로 입력받고 k번 수행 할 때 남은 요소들을 출력할 차례인데, 이 때 규칙을 보면 n개의 요소는 k(1부터시작)가 증가 할 때 마다 한개 씩 줄어듭니다. 

ex)k가 3일 때 

5,6,3,9,-1 -> 1,-3,6,-10 (4개) -> -4,3,-16 (3개) -> 7,-19 (2개)

즉, i~k번 연산하는 동안 n개의 요소들이 각각 변화하는 과정을 연산하되, 한번의 연산 후 요소의 개수가 한개 씩 줄어들어야합니다. 

결론적으로 18행이 그 연산코드입니다. 연산 후 조건에 맞게 출력하면됩니다.

코드

#pragma warning(disable:4996)
#include<iostream>
using namespace std;
int arr[21];
int main()
{
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++)
	{
		if (i < n - 1)
			scanf("%d,", &arr[i]);
		else
			scanf("%d", &arr[i]);
	}
	for (int i = 0; i < k; i++)
	{
		for (int j = 0; j <n-1-i;j++)
		{
			arr[j] = arr[j + 1] -arr[j];
		}
	}
	cout << arr[0];
	for (int i = 1; i < n - k; i++)
		cout << ',' << arr[i];
	cout << endl;
}

결과