나누어떨어짐

면접 대비

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

요약

수열과 정수 K가 주어질 때, 두 번째 원소부터 앞에 +나 -를 붙여 만든 합이 K로 나누어지는 경우가 있는지 판별한다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 수학, 정수론, 구현
정답자: 아직 제출이 없습니다

문제

정수들이 나열된 수열이 하나 주어진다. 수열에서 이웃한 정수들 사이에 + 또는 - 연산자를 넣으면 서로 다른 값을 가지는 여러 산술식을 만들 수 있다. 맨 앞 정수의 부호는 항상 +로 고정된다. 예를 들어 수열 17, 5, -21, 15를 생각하면 다음과 같이 여덟 가지 식을 만들 수 있다:

17 + 5 + -21 + 15 = 16
17 + 5 + -21 - 15 = -14
17 + 5 - -21 + 15 = 58
17 + 5 - -21 - 15 = 28
17 - 5 + -21 + 15 = 6
17 - 5 + -21 - 15 = -24
17 - 5 - -21 + 15 = 48
17 - 5 - -21 - 15 = 18

어떤 수열에 대해 + 또는 - 연산자를 적절히 넣어 식의 값이 $K$ 의 배수가 되도록 할 수 있으면, 그 수열은 $K$ 로 나누어떨어진다고 한다. 위 예에서 이 수열은 7로 나누어떨어지지만 (17 + 5 + -21 - 15 = -14) 5로는 나누어떨어지지 않는다.

주어진 정수 수열이 $K$ 로 나누어떨어지는지 판정하는 프로그램을 작성하라.

입력

첫째 줄에 두 정수 $N$ 과 $K$ 가 공백으로 구분되어 주어진다 ( $1 \le N \le 10000$ , $2 \le K \le 100$ ).

둘째 줄에 $N$ 개의 정수가 공백으로 구분되어 주어진다. 각 정수의 절댓값은 10000을 넘지 않는다.

출력

주어진 정수 수열이 $K$ 로 나누어떨어지면 "Divisible"을, 그렇지 않으면 "Not divisible"을 출력한다.

예제2

예제 1
입력
```
4 7
17 5 -21 15
```
예상 출력
```
Divisible
```
예제 2
입력
```
4 5
17 5 -21 15
```
예상 출력
```
Not divisible
```