| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 68 | 38 | 28 | 57.143% |
$0$과 $1$로만 구성된 두 문자열 $s_1$, $s_2$가 있다. 두 문자열의 길이는 $N$으로 같다.
이제 다음 두 가지 연산을 $0$회 이상 반복해 두 문자열의 모든 문자를 $1$로 만들려고 한다. 각 연산을 한 번 하는 데 소모되는 비용은 각각 $c_1$, $c_2$이다.
문자열 $S$의 $i$번째 문자를 반전하는 연산은 $S$의 $i$번째 문자가 $1$이라면 $0$으로 만들고, $0$이라면 $1$로 만드는 연산이다.
또한 문자열 $S$의 $L$번째 문자부터 $R$번째 문자까지 동시에 반전하는 연산은 $L\le i\le R$을 만족하는 모든 정수 $i$에 대해 동시에 문자열 $S$의 $i$번째 문자를 반전하는 연산이다.
$s_1$, $s_2$의 모든 문자를 $1$로 만드는 데 필요한 최소 비용을 구해 보자.
첫째 줄에 문자열 $s_1$과 $s_2$의 길이 $N$이 주어진다. $(1\le N\le 100\, 000)$
둘째 줄에 문자열 $s_1$이 주어진다.
셋째 줄에 문자열 $s_2$가 주어진다.
넷째 줄에 두 정수 $c_1$, $c_2$가 공백으로 구분되어 주어진다. $(1\le c_1, c_2 \le 10^9)$
$s_1$, $s_2$의 모든 문자를 $1$로 만드는 데 필요한 최소 비용을 출력한다.
5 00100 00011 10 1
21
다음과 같이 연산하는 경우, 소모되는 총 비용을 $21$로 하여 $s_1$, $s_2$ 의 모든 문자를 $1$로 만들 수 있다. 각 연산 수행 직후 바뀐 문자는 빨간색으로 표시한다.
$1$번째 연산: $s_1$의 $1$번째 문자부터 $5$번째 문자까지 반전한다. 이 때 소모되는 비용은 $10$이다.
$1$번째 연산을 수행한 결과는 아래와 같다.
| $s_1$ | $1$ | $1$ | $0$ | $1$ | $1$ |
| $s_2$ | $0$ | $0$ | $0$ | $1$ | $1$ |
$2$번째 연산: $s_2$의 $1$번째 문자부터 $2$번째 문자까지 반전한다. 이 때 소모되는 비용은 $10$이다.
$2$번째 연산을 수행한 결과는 아래와 같다.
| $s_1$ | $1$ | $1$ | $0$ | $1$ | $1$ |
| $s_2$ | $1$ | $1$ | $0$ | $1$ | $1$ |
$3$번째 연산: $s_1$과 $s_2$의 $3$번째 문자를 반전한다. 이 때 소모되는 비용은 $1$이다.
$3$번째 연산을 수행한 결과는 아래와 같다.
| $s_1$ | $1$ | $1$ | $1$ | $1$ | $1$ |
| $s_2$ | $1$ | $1$ | $1$ | $1$ | $1$ |
이 방법으로 연산하는 경우, 모든 문자를 $1$로 바꾸기까지 소모되는 총 비용은 $10 + 10 + 1 = 21$이다.
이보다 소모되는 비용을 더 적게 하여 모든 문자를 $1$로 만들 수 없음이 보장된다.
5 00100 00011 1 10
4
2 01 11 5 2
5
5 11111 11111 10 9
0
School > 대전과학고등학교 > 제2회 대전과학고등학교 프로그래밍 경진대회 DSHStack I번