세 개의 숫자 c0, c1 및 h와 이진 문자열 S가 있다고 가정합니다. S의 모든 비트를 뒤집을 수 있습니다. 각 변경에 대해 h 코인을 지불해야 합니다. 약간의 변경(0일 수도 있음) 후에 문자열을 구매하려고 합니다. 문자열을 구입하려면 문자열의 모든 문자를 구입해야 합니다. 비트 0을 사려면 c0 코인을 지불해야 하고 비트 1을 사려면 c1 코인을 지불해야 합니다. 문자열을 사는 데 필요한 최소 동전 수를 찾아야 합니다.
따라서 입력이 c0 =10과 같으면; c1 =100; h =1; S ="01010"이면 출력은 52가 됩니다. 먼저 S의 두 번째 및 네 번째 비트를 변경하고 이에 대해 2개의 코인을 지불하기 때문입니다. 이제 문자열은 00000이 됩니다. 그 후 문자열을 구매하고 5⋅10=50 코인을 지불할 수 있습니다. 지급되는 총 코인 수는 2+50=52입니다.
단계
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
k := 0 n := size of S for initialize i := 0, when i < n, update (increase i by 1), do: if S[i] is same as '0', then: k := k + minimum of c0 and (c1 + h) Otherwise k := k + minimum of (c0 + h) and c1 return k
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
int solve(int c0, int c1, int h, string S) {
int k = 0;
int n = S.size();
for (int i = 0; i < n; i++) {
if (S[i] == '0')
k = k + min(c0, c1 + h);
else
k = k + min(c0 + h, c1);
}
return k;
}
int main() {
int c0 = 10;
int c1 = 100;
int h = 1;
string S = "01010";
cout << solve(c0, c1, h, S) << endl;
} 입력
10, 100, 1, "01010"
출력
52