[문제출처 : Codechef] 한 초콜릿 가게에 방문하는 손님들은 특이한 특징이 있습니다. 바로 초콜릿을 사면서 필요없는 화폐를 내지 않는다는 점입니다. 즉, 바꿔말해, n개의 초콜릿을 산다고 했을 때, 손님이 낸 화폐들 중 어느 하나라도 제거했을 때 n개의 초콜릿을 살 수 없다는 이야기입니다.
점원은 손님들이 x원짜리 초콜릿을 몇개 사고싶어하는지 결정해야합니다. 만약 손님이 불가능한 조합으로 화폐를 줬다면 -1을, 가능한 조합이면 몇 개의 초콜릿을 원하는지 구하세요.
간단한 예제 케이스들을 들어보면, 화폐 [10, 4, 8, 5]가 있다고 가정합시다. 그리고 초콜릿 한 개의 가격은 7입니다. 그렇다면 화폐 전체의 합은 27이고, 초콜릿은 3개까지 살 수 있습니다. 하지만 이는 화폐 4나 5를 제거해도 마찬가지로 살 수 있는 개수입니다. 따라서 이것은 손님의 특징에 맞지 않으므로 -1을 리턴합니다.
다른 예제는 화폐 [12]가 있다고 가정합시다. 초콜릿 가격은 10입니다. 그러면 1개를 살 수 있고, 어느 화폐든지 하나를 제거하면 1개를 살 수 없게 됩니다. 따라서 손님이 원하는 것은 1개입니다.
마지막 예제는 화폐 [20, 50]이 있다고 가정하고, 초콜릿 가격은 10이라고 가정해 봅시다. 이 때 총 돈은 70이므로 7개의 초콜릿을 살 수 있습니다. 반면, 화폐 20을 제거하면 5개밖에 못사고, 50을 제거하면 2개밖에 못사므로 손님의 특징이 성립합니다. 따라서 손님은 7개의 초콜릿을 원합니다.
간단하게 생각해보면, 일단은 총 받은 화폐의 합으로 몇 개의 초콜릿을 살 수 있는지 구해야합니다. 그리고 각 화폐를 하나씩 제거해봤을 때에 같은 개수의 초콜릿을 살 수 있는 경우가 하나라도 나오면 -1을 리턴해야하고, 모든 경우 불가능할 시에 ‘합/초콜릿단가’를 리턴합니다.
그럼 각 화폐를 제거했을 때 같은 개수의 초콜릿을 살 수 있다는 얘기는 어떤 말일까요? 이것은 ‘합%초콜릿단가’보다 작거나 같은 화폐가 존재한다는 것과 같은 의미겠지요?(그러면 제거해도 여전히 같은 수의 초콜릿을 살 수 있을테니까요 ^^)
이것을 C언어 함수로 작성하면 다음과 같습니다.
#include <stdio.h>
void printMaxSweet(int *A, int N, int X){
int tot = 0;
for(int i=0;i<N;i++){
tot += A[i];
}
int remain = tot % X;
for(int i=0;i<N;i++){
if(A[i]<=remain){
printf("-1\n");
return;
}
}
printf("%d\n", tot/X);
}
int main(){
int N = 4;
int X = 7;
int A[N] = {10, 4, 8, 5};
printf("%d\n", printMaxSweet(A, N, X));
N = 1;
X = 10;
int A[N] = {12};
printf("%d\n", printMaxSweet(A, N, X));
N = 2;
X = 10;
int A[N] = {20, 50};
printf("%d\n", printMaxSweet(A, N, X));
return 0;
}
결과값:
-1
1
7