시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 56 24 22 42.308%

문제

2×N개의 전구가 두 줄로 놓여져 있다. 각 줄에는 N개의 전구가 있다. 각 전구는 상태는 켜져있거나 꺼져있다. 처음에 모든 전구는 꺼져있다.

현수는 일부 전구를 켜서 아름다운 패턴을 만드려고 한다. 현수는 행이나 열로 연속된 전구를 하나 이상 골라서 전구의 상태를 바꿀 수 있다. (꺼져있는 전구 -> 켬, 켜있는 전구 -> 끔)

현수가 만드려고 하는 패턴이 주어졌을 때, 최소 몇 번 만에 그 패턴을 만들 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 열의 크기 N이 주어진다. (1 ≤ N ≤ 10,000)

다음 두 줄에는 현수가 만드려고 하는 아름다운 패턴이 주어진다. 1은 전구가 켜져있는 상태이고, 0은 꺼져있는 상태이다. 

출력

현수가 최소 몇 번 만에 아름다운 패턴을 만들 수 있는지 출력한다.

예제 입력 1

20
11101101111000101010
01111101100000010100

예제 출력 1

7

힌트

W3sicHJvYmxlbV9pZCI6IjMxNTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MDRcdWFkNmMiLCJkZXNjcmlwdGlvbiI6IjxwPjImdGltZXM7Tlx1YWMxY1x1Yzc1OCBcdWM4MDRcdWFkNmNcdWFjMDAgXHViNDUwIFx1YzkwNFx1Yjg1YyBcdWIxOTNcdWM1ZWNcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVjOTA0XHVjNWQwXHViMjk0IE5cdWFjMWNcdWM3NTggXHVjODA0XHVhZDZjXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1YzgwNFx1YWQ2Y1x1YjI5NCBcdWMwYzFcdWQwZGNcdWIyOTQgXHVjZjFjXHVjODM4XHVjNzg4XHVhYzcwXHViMDk4IFx1YWViY1x1YzgzOFx1Yzc4OFx1YjJlNC4gXHVjYzk4XHVjNzRjXHVjNWQwIFx1YmFhOFx1YjRlMCBcdWM4MDRcdWFkNmNcdWIyOTQgXHVhZWJjXHVjODM4XHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ2MDRcdWMyMThcdWIyOTQgXHVjNzdjXHViZDgwIFx1YzgwNFx1YWQ2Y1x1Yjk3YyBcdWNmMWNcdWMxMWMgXHVjNTQ0XHViOTg0XHViMmU0XHVjNmI0IFx1ZDMyOFx1ZDEzNFx1Yzc0NCBcdWI5Y2NcdWI0ZGNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWQ2MDRcdWMyMThcdWIyOTQgXHVkNTg5XHVjNzc0XHViMDk4IFx1YzVmNFx1Yjg1YyBcdWM1ZjBcdWMxOGRcdWI0MWMgXHVjODA0XHVhZDZjXHViOTdjIFx1ZDU1OFx1YjA5OCBcdWM3NzRcdWMwYzEgXHVhY2U4XHViNzdjXHVjMTFjIFx1YzgwNFx1YWQ2Y1x1Yzc1OCBcdWMwYzFcdWQwZGNcdWI5N2MgXHViYzE0XHVhZmMwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIChcdWFlYmNcdWM4MzhcdWM3ODhcdWIyOTQgXHVjODA0XHVhZDZjIC0mZ3Q7IFx1Y2YyYywgXHVjZjFjXHVjNzg4XHViMjk0IFx1YzgwNFx1YWQ2YyAtJmd0OyBcdWIwNTQpPFwvcD5cclxuXHJcbjxwPlx1ZDYwNFx1YzIxOFx1YWMwMCBcdWI5Y2NcdWI0ZGNcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0IFx1ZDMyOFx1ZDEzNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWNkNWNcdWMxOGMgXHViYTg3IFx1YmM4OCBcdWI5Y2NcdWM1ZDAgXHVhZGY4IFx1ZDMyOFx1ZDEzNFx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNWY0XHVjNzU4IFx1ZDA2Y1x1YWUzMCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgXHViNDUwIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ2MDRcdWMyMThcdWFjMDAgXHViOWNjXHViNGRjXHViODI0XHVhY2UwIFx1ZDU1OFx1YjI5NCBcdWM1NDRcdWI5ODRcdWIyZTRcdWM2YjQgXHVkMzI4XHVkMTM0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gMVx1Yzc0MCBcdWM4MDRcdWFkNmNcdWFjMDAgXHVjZjFjXHVjODM4XHVjNzg4XHViMjk0IFx1YzBjMVx1ZDBkY1x1Yzc3NFx1YWNlMCwgMFx1Yzc0MCBcdWFlYmNcdWM4MzhcdWM3ODhcdWIyOTQgXHVjMGMxXHVkMGRjXHVjNzc0XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1ZDYwNFx1YzIxOFx1YWMwMCBcdWNkNWNcdWMxOGMgXHViYTg3IFx1YmM4OCBcdWI5Y2NcdWM1ZDAgXHVjNTQ0XHViOTg0XHViMmU0XHVjNmI0IFx1ZDMyOFx1ZDEzNFx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYnVsYi5wbmdcIiBzdHlsZT1cImhlaWdodDoxNDNweDsgd2lkdGg6NjQzcHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMxNTkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJsYW1waWNlIiwiZGVzY3JpcHRpb24iOiI8cD4yKk4gbGlnaHQgYnVsYnMgYXJlIGFycmFuZ2VkIGluIHR3byByb3dzIGFuZCBOIGNvbHVtbnMuIEVhY2ggbGlnaHQgYnVsYiBjYW4gYmUgZWl0aGVyIG9mZiBvciBvbiwgYW5kIGFsbCBsaWdodHMgYXJlIGluaXRpYWxseSBvZmYuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldlIHdhbnQgdG8gdHVybiBzb21lIG9mIHRoZW0gb24gc28gdGhhdCB0aGV5IGZvcm0gYSBiZWF1dGlmdWwgcGF0dGVybi4gSW4gb25lIHN0ZXAgd2UgY2FuIGNoYW5nZSB0aGUgc3RhdGUgb2YgYSBzZXF1ZW5jZSBvZiAob25lIG9yIG1vcmUpIGNvbnNlY3V0aXZlIGxpZ2h0IGJ1bGJzIGluIHRoZSBzYW1lIHJvdyBvciBjb2x1bW4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkdpdmVuIHRoZSBkZXNpcmVkIHBhdHRlcm4sIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IGZpbmRzIHRoZSBtaW5pbXVtIG51bWJlciBvZiBzdGVwcyByZXF1aXJlZCB0byBmb3JtIHRoZSBwYXR0ZXJuLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYW4gaW50ZWdlciBOLCAxICZsZTsgTiAmbGU7IDEwLDAwMCwgdGhlIG51bWJlciBvZiBjb2x1bW5zLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgdHdvIGxpbmVzIGNvbnRhaW5zIGEgc2VxdWVuY2Ugb2YgTiBjaGFyYWN0ZXJzIHJlcHJlc2VudGluZyB0aGUgZGVzaXJlZCBmaW5hbCBwYXR0ZXJuLiZuYnNwOzxcL3A+XHJcblxyXG48cD5DaGFyYWN0ZXIgJiMzOTsxJiMzOTsgaW5kaWNhdGVzIGEgbGlnaHQgYnVsYiB0aGF0IHNob3VsZCBiZSBvbiBpbiB0aGUgZmluYWwgc3RhdGUsIHdoaWxlIHRoZSBjaGFyYWN0ZXIgJiMzOTswJiMzOTsgaW5kaWNhdGVzIGEgbGlnaHQgYnVsYiB0aGF0IHNob3VsZCBiZSBvZmYuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIGEgc2luZ2xlIGludGVnZXIgJm5kYXNoOyB0aGUgbWluaW11bSBudW1iZXIgb2Ygc3RlcHMgcmVxdWlyZWQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPlRoZSBmb2xsb3dpbmcgZmlndXJlIGlsbHVzdHJhdGVzIHRoZSBzZXZlbiBzdGVwcyBuZWVkZWQgdG8gb2J0YWluIHRoZSBwYXR0ZXJuIGdpdmVuIGluIHRoZSBleGFtcGxlOiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2J1bGIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTQzcHg7IHdpZHRoOjY0M3B4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=