문제 개요
세 개의 숫자 c0, c1, h와 바이너리(이진) 문자열 S가 주어집니다. 우리는 S의 임의의 비트를 자유롭게 뒤집을 수 있으며, 비트 하나를 변경할 때마다 h개의 동전을 지불해야 합니다. 몇 번의 변경(변경하지 않아도 됨)을 거친 뒤 문자열을 구매하려고 합니다.
문자열을 구매하려면 문자열을 구성하는 모든 문자를 구입해야 합니다. 비트 0 하나를 구매할 때는 c0개의 동전을, 비트 1 하나를 구매할 때는 c1개의 동전을 지불합니다. 이때 문자열 전체를 구매하는 데 필요한 최소 동전 수를 구하는 것이 목표입니다.
예시
입력이 c0 = 10, c1 = 100, h = 1, S = "01010"이라고 가정해 보겠습니다. 이 경우 출력은 52가 됩니다. 먼저 S의 2번째와 4번째 비트를 뒤집고 2개의 동전을 지불하면 문자열은 "00000"이 됩니다. 이후 문자열을 구매하며 5 × 10 = 50개의 동전을 지불합니다. 따라서 총 지불 금액은 2 + 50 = 52입니다.
풀이 접근 방법
이 문제의 핵심은 각 비트마다 두 가지 선택지를 비교하는 것입니다. 해당 비트를 그대로 구매하는 것이 저렴한지, 아니면 비용 h를 들여 뒤집은 다음 구매하는 것이 저렴한지 판단하면 됩니다.
- 비트가 '0'인 경우: 그대로 구매하면 c0, 뒤집어서 '1'로 만든 뒤 구매하면 c1 + h이므로, 두 값 중 최솟값을 더합니다.
- 비트가 '1'인 경우: 그대로 구매하면 c1, 뒤집어서 '0'으로 만든 뒤 구매하면 c0 + h이므로, 두 값 중 최솟값을 더합니다.
모든 비트에 대해 위 과정을 수행한 결과를 합산하면 곧 최소 동전 수가 됩니다. 이를 의사 코드로 표현하면 다음과 같습니다.
k := 0
n := S의 길이
i := 0부터 시작하여 i < n인 동안 i를 1씩 증가시키며 반복:
만약 S[i]가 '0'과 같다면:
k := k + (c0와 (c1 + h) 중 최솟값)
그렇지 않으면:
k := k + ((c0 + h)와 c1 중 최솟값)
k 반환C++ 구현 코드
위 로직을 실제 C++ 코드로 구현하면 다음과 같습니다.
#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
이 알고리즘은 문자열의 길이에 비례하여 한 번만 순회하면 되므로 시간 복잡도는 O(n)이며, 추가 메모리 사용 없이 효율적으로 최소 비용을 계산할 수 있습니다.