수식 고치기

면접 대비

시간 제한2초메모리 제한1024 MB

요약

좌에서 우로 계산되는 T/F 식에서 값과 연산자를 최소로 바꿔 목표 결과 C를 얻는 횟수를 구합니다.

난이도: 보통10점 중 4점
유형: 동적 계획법
정답자: 아직 제출이 없습니다

문제

T | F | T & F | T & F

위 식처럼 값은 T와 F, 연산자는 |과 &로만 이루어진 수식이 주어진다. | 연산은 두 피연산자 중 하나 이상이 T이면 T이고, 그렇지 않으면 F이다. & 연산은 두 피연산자가 모두 T이면 T이고, 그렇지 않으면 F이다. |과 &의 우선순위는 같고, 식은 왼쪽에서 오른쪽으로 계산한다.

연산자와 값을 적절히 바꾸어 원하는 계산 결과가 나오도록 해야 한다. 이때 바꾸는 연산자와 값의 개수를 최소화해야 한다. 식과 원하는 계산 결과가 주어졌을 때, 결과가 나오도록 연산자와 값을 고치는 최소 횟수를 구한다.

입력

첫째 줄에 식에 있는 값의 개수와 연산자의 개수를 더한 정수 $N$ 이 주어진다.

둘째 줄에 $N$ 개의 문자 $A_1, A_2, \cdots, A_N$ 이 공백으로 구분되어 주어진다. $i$ 가 홀수면 $A_i$ 는 값이고, $i$ 가 짝수면 $A_i$ 는 연산자이다.

셋째 줄에 원하는 계산 결과를 나타내는 문자 $C$ 가 주어진다.

출력

원하는 계산 결과가 나오도록 값과 연산자를 고치는 최소 횟수를 출력한다.

제한

$1 \le N \le 1999$ , $N$ 은 홀수
$i$ 가 홀수면 $A_i \in \{\mathrm{T}, \mathrm{F}\}$ ( $1 \le i \le N$ )
$i$ 가 짝수면 $A_i \in \{\texttt{\&}, \texttt{|}\}$ ( $1 \le i \le N$ )
$C \in \{\mathrm{T}, \mathrm{F}\}$

예제4

예제 1
입력
```
9
T & F | F | T & F
T
```
예상 출력
```
1
```
예제 2
입력
```
3
F & F
T
```
예상 출력
```
2
```
예제 3
입력
```
1
T
T
```
예상 출력
```
0
```
예제 4
입력
```
1
T
F
```
예상 출력
```
1
```