시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 177 | 70 | 60 | 40.816% |
긴 복도에 $N$개의 램프가 일렬로 나열되어 있다. 램프는 왼쪽부터 차례로 1번부터 $N$번까지의 번호가 붙어있다. 각 램프는 off또는 on중 하나의 상태이다.
램프의 상태를 바꾸는 특별한 기작이 있어서, 한 번의 작업으로 다음 셋 중 한 가지 동작을 할 수 있다.
처음에 램프의 상태는 길이 $N$의 문자열 $A$로 표현된다. $A$의 $i$ 번째 ($1 \le i \le N$) 문자가 0
이면 $i$ 번째 램프가 off 상태인 것이고, 1
이면 on 상태인 것이다. 우리는 만들고 싶은 상태가 길이 $N$의 문자열 $B$로 표현 되어 있고, 작업의 수를 최소한으로 하여 만들고 싶다. $B$의 $i$ 번째 ($1 \le i \le N$) 문자가 0
이면 $i$ 번째 램프가 off 상태인 것이고, 1
이면 on 상태인 것이다.
램프의 수와, 현재 상태와 만들고 싶은 상태가 주어졌을 때, 만들고 싶은 상태로 바꾸는 데에 드는 연산의 수의 최솟값을 출력하여라.
표준 입력에서 다음과 같은 형식으로 주어진다.
$N$
$A$
$B$
표준 출력으로 한 개의 줄을 출력하여라. 이는 원하는 상태를 만들기 위한 연산의 수의 최솟값이다.
0
혹은 1
이다.번호 | 배점 | 제한 |
---|---|---|
1 | 6 | N ≤ 18. |
2 | 41 | N ≤ 2 000. |
3 | 4 | Each character in A is |
4 | 49 | No additional constraints. |
8 11011100 01101001
4
이 입력에서 우리는 원하는 상태를 다음과 같은 방법으로 네 번의 작업으로 만들 수 있다.
네 번보다 더 적은 작업으로 원하는 상태를 만들 수 있는 방법은 없으므로, 4를 출력한다.
13 1010010010100 0000111001011
3
18 001100010010000110 110110001000100101
5