3회 문제풀이 15 / ABC 119 C - Synthetic Kadomatsu
ABC 119 C - Synthetic Kadomatsu
【문제 개요】
당신은 N개의 대나무를 가지고 있습니다. 각각의 길이는 l1, l2, …, lN입니다.(단위 : 센티미터)
당신의 목적은 이 대나무중 몇개를 (전부 선택할수도 있다) 사용하여 길이가 A, B, C가 되도록 3개의 대나무를 만들것이다. 이를 위하여 이하의 3종류의 마법을 임의의 순서로 몇번이라도 사용할 수 있다.
- 연장 마법 : 1MP(매직 포인트)를 소비하여 1개의 대나무를 선택하여 그 길이를 1 늘린다.
- 단축 마법 : 1MP를 소비하여 길이 2 이상의 대나무 1개를 선택하여 길이를 1 줄인다.
- 합성 마법 : 10MP를 소비하여 2개의 대나무를 선택하여 연결해 1개의 대나무로 한다. 이 새로운 대나무의 길이는 연결에 사용된 2개의 대나무의 길이의 합계와 동일하다. 목적을 달성하기 위해서는 최소 몇의 MP가 필요한가?
【전제】
- 3 ≦ N ≦ 8
- 1 ≦ C < B < A ≦ 1000
- 1 ≦ li ≦ 1000
- 입력은 모두 정수이다.
【입력 형태】
1
2
3
4
5
N A B C
l1
l2
...
lN
【출력 형태】
목적의 달성에 필요한 MP의 최소값을 출력하라.
【예시】
입력 예 1
1
2
3
4
5
6
5 100 90 80
98
40
30
21
80
출력 예 1
1
23
길이 98, 40, 30, 21, 80의 5개의 대나무를 길이 100, 90, 80의 3개의 대나무를 얻으려고 합니다.
길이 80 대나무는 처음부터 가지고 있으며, 길이 100, 90의 대나무는 다음과 같이 마법을 사용하면 합계 23MP를 소비함으로써 얻을 수 있으며, 이것이 가장 최선입니다.
- 길이 98의 대나무에 연장 마법을 2회 사용하여 길이 100의 대나무를 획득한다. (소비 MP : 2)
- 길이 40, 30의 대나무에 합성 마법을 사용하여, 길이 70의 대나무를 획득한다. (소비 MP : 10)
- 길이 21의 대나무에 단축 마법을 1회 사용하여, 길이 20의 대나무를 획득한다. (소비 MP : 1)
- 순서 2에서 얻은 길이 70의 대나무와 순서 3에서 얻은 20의 대나무로 합성 마법을 사용하여, 길이 90의 대나무를 획득한다. (소비 MP : 10)
입력 예 2
1
2
3
4
5
6
7
8
9
8 100 90 80
100
100
90
90
90
80
80
80
출력 예 2
1
0
원하는 길이의 대나무를 이미 전부 가지고있기 때문에 필요한 MP는 0입니다. 이처럼 반드시 막대기를 전부 사용할 필요는 없습니다.
입력 예 3
1
2
3
4
5
6
7
8
9
8 1000 800 100
300
333
400
444
500
555
600
666
출력 예 3
1
243
ABC 119 C - Synthetic Kadomatsu
【문제 개요】
당신은 N개의 대나무를 가지고 있습니다. 각각의 길이는 l1, l2, …, lN입니다.(단위 : 센티미터)
당신의 목적은 이 대나무중 몇개를 (전부 선택할수도 있다) 사용하여 길이가 A, B, C가 되도록 3개의 대나무를 만들것이다. 이를 위하여 이하의 3종류의 마법을 임의의 순서로 몇번이라도 사용할 수 있다.
- 연장 마법 : 1MP(매직 포인트)를 소비하여 1개의 대나무를 선택하여 그 길이를 1 늘린다.
- 단축 마법 : 1MP를 소비하여 길이 2 이상의 대나무 1개를 선택하여 길이를 1 줄인다.
- 합성 마법 : 10MP를 소비하여 2개의 대나무를 선택하여 연결해 1개의 대나무로 한다. 이 새로운 대나무의 길이는 연결에 사용된 2개의 대나무의 길이의 합계와 동일하다. 목적을 달성하기 위해서는 최소 몇의 MP가 필요한가?
【전제】
- 3 ≦ N ≦ 8
- 1 ≦ C < B < A ≦ 1000
- 1 ≦ li ≦ 1000
- 입력은 모두 정수이다.
【입력 형태】
1
2
3
4
5
N A B C
l1
l2
...
lN
【출력 형태】
목적의 달성에 필요한 MP의 최소값을 출력하라.
【예시】
입력 예 1
1
2
3
4
5
6
5 100 90 80
98
40
30
21
80
출력 예 1
1
23
길이 98, 40, 30, 21, 80의 5개의 대나무를 길이 100, 90, 80의 3개의 대나무를 얻으려고 합니다.
길이 80 대나무는 처음부터 가지고 있으며, 길이 100, 90의 대나무는 다음과 같이 마법을 사용하면 합계 23MP를 소비함으로써 얻을 수 있으며, 이것이 가장 최선입니다.
- 길이 98의 대나무에 연장 마법을 2회 사용하여 길이 100의 대나무를 획득한다. (소비 MP : 2)
- 길이 40, 30의 대나무에 합성 마법을 사용하여, 길이 70의 대나무를 획득한다. (소비 MP : 10)
- 길이 21의 대나무에 단축 마법을 1회 사용하여, 길이 20의 대나무를 획득한다. (소비 MP : 1)
- 순서 2에서 얻은 길이 70의 대나무와 순서 3에서 얻은 20의 대나무로 합성 마법을 사용하여, 길이 90의 대나무를 획득한다. (소비 MP : 10)
입력 예 2
1
2
3
4
5
6
7
8
9
8 100 90 80
100
100
90
90
90
80
80
80
출력 예 2
1
0
원하는 길이의 대나무를 이미 전부 가지고있기 때문에 필요한 MP는 0입니다. 이처럼 반드시 막대기를 전부 사용할 필요는 없습니다.
입력 예 3
1
2
3
4
5
6
7
8
9
8 1000 800 100
300
333
400
444
500
555
600
666
출력 예 3
1
243