17675번 - 램프 출처다국어분류
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 51 | 32 | 28 | 60.870% |
문제
긴 복도에 $N$개의 램프가 일렬로 나열되어 있다. 램프는 왼쪽부터 차례로 1번부터 $N$번까지의 번호가 붙어있다. 각 램프는 off또는 on중 하나의 상태이다.
램프의 상태를 바꾸는 특별한 기작이 있어서, 한 번의 작업으로 다음 셋 중 한 가지 동작을 할 수 있다.
- $1 \le p \le q \le N$을 만족하는 정수 $p$와 $q$를 골라서 $p$, $p+1$, $\cdots$, $q$를 off 상태로 만든다.
- $1 \le p \le q \le N$을 만족하는 정수 $p$와 $q$를 골라서 $p$, $p+1$, $\cdots$, $q$를 on 상태로 만든다.
- $1 \le p \le q \le N$을 만족하는 정수 $p$와 $q$를 골라서 $p$, $p+1$, $\cdots$, $q$의 상태를 바꾼다. (off를 on으로, on을 off로)
처음에 램프의 상태는 길이 $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$
출력
표준 출력으로 한 개의 줄을 출력하여라. 이는 원하는 상태를 만들기 위한 연산의 수의 최솟값이다.
제한
- $1 \le N \le 1\ 000\ 000$.
- $A$와 $B$는 길이 $N$의 문자열이다.
- $A$와 $B$를 이루는 문자들은 0 혹은 1이다.
예제 입력 1
8 11011100 01101001
예제 출력 1
4
이 입력에서 우리는 원하는 상태를 다음과 같은 방법으로 네 번의 작업으로 만들 수 있다.
- 1, 2, 3, 4번 램프의 상태를 바꾼다. 램프의 상태는 00101100이 된다.
- 2번 램프를 on 상태로 만든다. 램프의 상태는 01101100이 된다.
- 6, 7, 8번 램프의 상태를 바꾼다. 램프의 상태는 01101011이 된다.
- 6, 7번 램프를 off 상태로 만든다. 램프의 상태는 01101001이 된다.
네 번보다 더 적은 작업으로 원하는 상태를 만들 수 있는 방법은 없으므로, 4를 출력한다.
예제 입력 2
13 1010010010100 0000111001011
예제 출력 2
3
예제 입력 3
18 001100010010000110 110110001000100101
예제 출력 3
5
© 2021 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호
