2001년 가을학기 문제해결기법 - 문제 3

수열 추정

감소하지 않는 수열의 일부가 주어져 있다. 현재 주어진 수열의 마지막 수 다음 수들은 무엇인지를 추정하고자 한다. 수열에서 수를 추정할 때 다음과 같이 수의 차를 이용하는 방식이 있다. 이 방식을 예를 들어 설명하기로 한다. 수열 3, 6, 10, 15가 주어져 있다고 하자. 이 수열의 차를 한번 구하고, 원소의 수가 둘 이상이면 다음과 같이 이 과정을 반복한다.

3    6   10   15

3    4    5

1    1

0

위 수열에서 5번째 수를 추정하기 위해서 마지막 행은 상수로 모두 같은 수가 반복된다고 가정한다. 위에 예에서는 아래와 같이 마지막 행에 0을 추가하고, 역으로 계산하여 5번째 원소가 21이라고 추정할 수 있다.

3    6   10   15   21

3    4    5    6

1    1    1

0    0

입력으로 길이가 [eqn: n]인 수열과 양의 정수 [eqn: k]가 주어질 때, 이 수열에서[eqn: n+1]번째 수부터 [eqn: n+k]번째까지 [eqn: k]개의 수를 추정하여 출력하는 프로그램을 작성하시오. [eqn: n]과 [eqn: k]는 모두 10,000 이하라고 가정한다.

프로그램명은 seq.c(seq.cpp)라고 하고 실행 파일명은 seq.exe로 한다. 프로그램의 실행 시간은 5초를 초과할 수 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT이다.

첫줄에는 주어지는 수열의 길이 [eqn: n]과 추정할 수의 갯수 [eqn: k]가 입력된다. 둘째 줄에는 수열에 속한 수가 차례로 [eqn: n]개 주어진다. 이들 사이에는 콤마가 없고 공백이 하나 혹은 그 이상 있다.

출력 형식

출력 파일의 이름은 OUTPUT.TXT이다. 첫 줄에 추정한 [eqn: k]개의 수를 [eqn: n+1]번째 수부터 시작하여 [eqn: n+k]번째 수까지 출력한다. 출력하는 수 사이에 공백이 하나 있다.

입력과 출력의 예

INPUT.TXT

4 2

3 6 10 15

OUTPUT.TXT

21 28