문제 :
초콜릿을 좋아하는 안나는 지금 책상 앞에 있다.
책상에는 N개의 상자가 있다.
상자 안에는 각각 다 초콜릿이 들어있다.
안나는 각 상자에 사탕이 몇개 있는지 모르지만, 이 정보는 알고있다
상자에 들어있는 초콜릿의 개수의 합은 C개이다.
상자\'i\'에 들어있는 초콜릿의 수는 최소 low[i]개, 최대 high[i]개이다. (0부터 시작하는 행렬)
안나는 이 행동을 한다. :
한 세트의 박스를 고르고, 모두 열어서, 그 안에 있는 모든 초콜릿을 먹는다.
안나는 최소한 X개의 초콜릿을 먹고싶어한다.
안나는 똑똑해서, 항상 총 X개 이상의 초콜릿이 들어있는 상자들을 고른다.
당신에게 C와 X, 그리고 low[], high[]가 주어진다.
고를수 있는 상자 개수의 최솟값을 구하는 알고리즘, 코드를 제시하여라.
형식 :
함수명 : minBoxes
인수 : int, int, int[], int[], int (C++/C : int
반환값 : int
함수 형태 : int minBoxes(int C, int X, int[] low, int[] high, int arrlen)
값 설명 :
C(인자 1) : 초콜릿 개수의 합. C는 모든 high 값의합보다 작다.
X(인자 2) : 안나가 먹고싶어하는 초콜릿의 개수
low[](인자 3) : low[i] = i번 상자에 들어있는 초콜릿 개수의 최소값
high[](인자 4) : high[i] = i번 상자에 들어있는 초콜릿 개수의 최댓값
arrlen(인자 5) : java에서는 제외 가능, low와 high 행렬의 길이(0부터 시작), C유저들을 배려하여 만들어진 인자
예제 :
1)
minBoxes(15 , 12 , {1,2,3,4,5}, {1,2,3,4,5}, 4 );
반환값 : 3
(각 3,4,5개 들어있는) 2,3,4번 박스 선택. 3+4+5 = 정확히 12개의 초콜릿
2)
minBoxes(60 , 8 , {5,2,3}, {49, 48, 47}, 2 );
반환값 : 2
0번과 2번 선택.
3) 프로그램 테스트용
<blockquote>
minboxes(207581165, 172146543, {4725448, 2753824, 6019698, 4199708, 4070001, 3589497, 5358499, 3637585, 5393667, 2837466, 2747807, 2918199, 3638042, 5199002, 3072044, 3858909, 3762101, 3657754, 3218704, 3888861, 3195689, 4768935, 3137633, 4124272, 4125056, 6087486, 3632970, 3620489, 2748765, 5917493, 3958996, 3335021, 3517186, 5543440, 2951006, 3403270, 3299481, 3093204, 4092331}, {5702812, 6805664, 6823687, 5337687, 4286533, 4999849, 6567411, 4563235, 6618139, 6260135, 6249469, 3821449, 5963157, 6385012, 4255959, 5786920, 6112817, 4103918, 6371537, 4231698, 3409172, 6806782, 5623563, 4511221, 6407338, 6491490, 5209517, 6076093, 6530132, 6111464, 5833839, 6253088, 5595160, 6236805, 5772388, 5285713, 5617002, 4650978, 5234740}, 38);
</blockquote>
반환값 : 31
P.S. : 야! 내가 프폭도다!
형들 이 문제 뭐라하는건지 이해가?
엘-멘
초콜릿을 좋아하는 안나는 지금 책상 앞에 있다.
책상에는 N개의 상자가 있다.
상자 안에는 각각 다 초콜릿이 들어있다.
안나는 각 상자에 사탕이 몇개 있는지 모르지만, 이 정보는 알고있다
상자에 들어있는 초콜릿의 개수의 합은 C개이다.
상자\'i\'에 들어있는 초콜릿의 수는 최소 low[i]개, 최대 high[i]개이다. (0부터 시작하는 행렬)
안나는 이 행동을 한다. :
한 세트의 박스를 고르고, 모두 열어서, 그 안에 있는 모든 초콜릿을 먹는다.
안나는 최소한 X개의 초콜릿을 먹고싶어한다.
안나는 똑똑해서, 항상 총 X개 이상의 초콜릿이 들어있는 상자들을 고른다.
당신에게 C와 X, 그리고 low[], high[]가 주어진다.
고를수 있는 상자 개수의 최솟값을 구하는 알고리즘, 코드를 제시하여라.
형식 :
함수명 : minBoxes
인수 : int, int, int[], int[], int (C++/C : int
반환값 : int
함수 형태 : int minBoxes(int C, int X, int[] low, int[] high, int arrlen)
값 설명 :
C(인자 1) : 초콜릿 개수의 합. C는 모든 high 값의합보다 작다.
X(인자 2) : 안나가 먹고싶어하는 초콜릿의 개수
low[](인자 3) : low[i] = i번 상자에 들어있는 초콜릿 개수의 최소값
high[](인자 4) : high[i] = i번 상자에 들어있는 초콜릿 개수의 최댓값
arrlen(인자 5) : java에서는 제외 가능, low와 high 행렬의 길이(0부터 시작), C유저들을 배려하여 만들어진 인자
예제 :
1)
minBoxes(15 , 12 , {1,2,3,4,5}, {1,2,3,4,5}, 4 );
반환값 : 3
(각 3,4,5개 들어있는) 2,3,4번 박스 선택. 3+4+5 = 정확히 12개의 초콜릿
2)
minBoxes(60 , 8 , {5,2,3}, {49, 48, 47}, 2 );
반환값 : 2
0번과 2번 선택.
3) 프로그램 테스트용
<blockquote>
minboxes(207581165, 172146543, {4725448, 2753824, 6019698, 4199708, 4070001, 3589497, 5358499, 3637585, 5393667, 2837466, 2747807, 2918199, 3638042, 5199002, 3072044, 3858909, 3762101, 3657754, 3218704, 3888861, 3195689, 4768935, 3137633, 4124272, 4125056, 6087486, 3632970, 3620489, 2748765, 5917493, 3958996, 3335021, 3517186, 5543440, 2951006, 3403270, 3299481, 3093204, 4092331}, {5702812, 6805664, 6823687, 5337687, 4286533, 4999849, 6567411, 4563235, 6618139, 6260135, 6249469, 3821449, 5963157, 6385012, 4255959, 5786920, 6112817, 4103918, 6371537, 4231698, 3409172, 6806782, 5623563, 4511221, 6407338, 6491490, 5209517, 6076093, 6530132, 6111464, 5833839, 6253088, 5595160, 6236805, 5772388, 5285713, 5617002, 4650978, 5234740}, 38);
</blockquote>
반환값 : 31
P.S. : 야! 내가 프폭도다!
형들 이 문제 뭐라하는건지 이해가?
엘-멘
댓글 0