수열 축소 > 문제은행

본문 바로가기


알고리즘 다이나믹2

1389 : 수열 축소

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 76 회    시도횟수: 239 회    Special Judge



n개의 정수들로 이루어진 수열[a1 a2 ... an]이 있다. 여기에 정수 i를 주면서 '축소'라는 명령을 하면 ai와 ai+1이 없어지고 대신 두 수의 차가 들어간다. 즉 새로 들어간 수는 |ai-ai+1|이다. 바꿔 말하면 축소 연산 i는축소 ([a1, a2, ..., an] i) = [a1 ... ai-1|ai-ai+1|ai+2 ... an] 이다. 단 1≤i≤n-1.

 

예를 들어, 수열 [12, 10, 4, 3, 5]에 축소 연산들 2, 3, 2, 1을 차례대로 적용하면
축소([12, 10, 4, 3, 5], 2) = [12, 6, 3, 5]
축소([12, 6, 3, 5], 3) = [12, 6, 2]
축소([12, 6, 2], 2) = [12, 4]
축소([12, 4], 1) = [8]이 되므로,
마지막에 8이 남는다.

 

같은 수열에 축소 연산 1, 1, 1, 1을 적용하며,
축소([12, 10, 4, 3, 5], 1) = [2, 4, 3, 5]
축소([2, 4, 3, 5], 1) = [2, 3, 5]
축소([2, 3, 5], 1) = [1, 5]
축소([1, 5], 1) = [4]가 되므로,
마지막에 4가 남는다.

 

입력으로 수열과 최종값이 주어질 때, n-1번의 축소 연산을 수행하여 최종값을 얻을수 있는가를 알아내는 프로그램을 작성하시오. 최종값을 얻을 수 있는 축소연산들이 여러개일 경우는 그 중 하나만 출력한다.


첫줄에는 정수 N(1≤N≤30)이 주어진다. 둘째 줄에는 최종값이 주어진다.
다름 N줄에는 a1, a2, ..., an에 해당하는 수가 한 줄에 하나씩 순서대로 주어진다.(각 ai는 1 이상 30 이하)


첫 줄부터 구한 축소연산들을 한 줄에 하나씩 순서대로 출력한다. 최종값을 구할 수 없는 경우에는 첫줄에 0을 출력한다.

[Copy]
5
8
12
10
4
3
5
[Copy]
2
3
2
1


[Copy]
4
7
12
10
4
5
[Copy]
0





HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.