연산 기호

면접 대비

시간 제한1초메모리 제한1024 MB

요약

인접한 수 사이에 + 또는 -를 넣어 왼쪽에서 오른쪽으로 계산한 값이 목표값이 되게 하되, 모든 중간 결과의 절댓값이 10000 이하인 식 중 사전순으로 가장 앞서는 식을 출력한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 백트래킹, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

양의 정수로 이루어진 수열과 양의 정수 목표값이 주어진다. 수열의 각 숫자 사이에 더하기(+) 또는 빼기(-) 기호를 넣어, 왼쪽에서 오른쪽으로 계산한 식의 값이 목표값과 같아지도록 만들려고 한다. 첫 번째 숫자 앞에는 기호를 붙이지 않는다.

입력

첫째 줄에 수열의 길이 $N$ ( $1 \le N \le 1000$ )이 주어진다. 둘째 줄에 수열의 원소가 공백으로 구분되어 주어진다. 셋째 줄에 목표값이 주어진다. 수열의 원소와 목표값은 모두 $1$ 이상 $10000$ 이하이다.

출력

숫자를 주어진 순서대로 두고 그 사이에 + 또는 - 기호를 넣어 만든 식을 한 줄에 출력한다(첫 번째 숫자 앞에는 기호가 없다). 단, 왼쪽에서 오른쪽으로 계산할 때 모든 중간 결과의 절댓값이 $10000$ 을 넘지 않는 식만 고려한다. 그러한 식은 적어도 하나 존재함이 보장된다. 조건을 만족하는 식이 여러 개라면, 그중 문자열을 사전순으로 비교했을 때 가장 작은 것을 출력한다(+가 -보다 작다고 본다).

예제5

예제 1
입력
```
5
5 4 3 2 1
5
```
예상 출력
```
5+4-3-2+1
```
예제 2
입력
```
2
3 5
8
```
예상 출력
```
3+5
```
예제 3
입력
```
2
5 3
2
```
예상 출력
```
5-3
```
예제 4
입력
```
3
10 20 30
20
```
예상 출력
```
10-20+30
```
예제 5
입력
```
4
1 1 1 1
2
```
예상 출력
```
1+1+1-1
```