문제 설명
정보 선생님은 정보 수업에 열심히 참여한 세종이에게 사탕 선물을 준비했다.
다만 조건이 하나 있었는데 사탕을 마음껏 고를 수 있지만, 고른 사탕의 무게의 합이 M그램(g)을 만족해야 한다는 것이다. 만약 사탕들의 무게 합이 조금이라도 무겁거나 가볍다면 사탕을 가질 수 없다.
선생님이 준비한 6개의 사탕 무게가 각 1g, 2g, 3g, 4g, 5g, 7g이고 선생님이 제시한 무게가 7g이라면 (3g, 4g)을 선택하여 사탕을 가져갈 수 있지만 (1g, 5g)을 선택하면 사탕을 가질 수 없게 된다.
사탕의 개수 N과 각 사탕의 무게, 그리고 무게 M이 주어질 때, 세종이가 사탕을 가져갈 수 있는 방법의 개수를 출력하시오.
만약 세종이가 사탕을 가져갈 수 없는 경우에는 -1을 출력하시오.
다만 조건이 하나 있었는데 사탕을 마음껏 고를 수 있지만, 고른 사탕의 무게의 합이 M그램(g)을 만족해야 한다는 것이다. 만약 사탕들의 무게 합이 조금이라도 무겁거나 가볍다면 사탕을 가질 수 없다.
선생님이 준비한 6개의 사탕 무게가 각 1g, 2g, 3g, 4g, 5g, 7g이고 선생님이 제시한 무게가 7g이라면 (3g, 4g)을 선택하여 사탕을 가져갈 수 있지만 (1g, 5g)을 선택하면 사탕을 가질 수 없게 된다.
사탕의 개수 N과 각 사탕의 무게, 그리고 무게 M이 주어질 때, 세종이가 사탕을 가져갈 수 있는 방법의 개수를 출력하시오.
만약 세종이가 사탕을 가져갈 수 없는 경우에는 -1을 출력하시오.
입력 설명
첫째 줄에는 사탕의 개수\((N)\)가 주어진다.\((1 \le N \le 20)\)
둘째 줄에는 각 사탕의 무게\((C_i)\)가 공백으로 구분되어 주어진다.\((1 \le C_i \le 1,000)\)
마지막 줄에는 무게\((M)\)가 주어진다.\((1 \le M \le 10,000)\)
둘째 줄에는 각 사탕의 무게\((C_i)\)가 공백으로 구분되어 주어진다.\((1 \le C_i \le 1,000)\)
마지막 줄에는 무게\((M)\)가 주어진다.\((1 \le M \le 10,000)\)
출력 설명
세종이가 사탕을 가져갈 수 있는 방법의 개수를 출력한다.
입력 예시 Copy
6
1 2 3 4 5 7
7
출력 예시 Copy
4