시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB72333145.588%

문제

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

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

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

입력

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

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

출력

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

예제 입력 1

3
100
000

예제 출력 1

1

예제 입력 2

5
11011
11011

예제 출력 2

3

예제 입력 3

20
11101101111000101010
01111101100000010100

예제 출력 3

7
0 1 2 3
00000000000000000000
00000000000000000000
11100000000000000000
00000000000000000000
11100010000000000000
00000010000000000000
11100010000000000000
01111101100000000000
4 5 6 7
11101101111000000000
01111101100000000000
11101101111000111110
01111101100000000000
11101101111000101110
01111101100000010000
11101101111000101010
01111101100000010100
W3sicHJvYmxlbV9pZCI6IjMxNTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MDRcdWFkNmMiLCJkZXNjcmlwdGlvbiI6IjxwPjImdGltZXM7Tlx1YWMxY1x1Yzc1OCBcdWM4MDRcdWFkNmNcdWFjMDAgXHViNDUwIFx1YzkwNFx1Yjg1YyBcdWIxOTNcdWM1ZWNcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVjOTA0XHVjNWQwXHViMjk0IE5cdWFjMWNcdWM3NTggXHVjODA0XHVhZDZjXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1YzgwNFx1YWQ2Y1x1YjI5NCBcdWMwYzFcdWQwZGNcdWIyOTQgXHVjZjFjXHVjODM4XHVjNzg4XHVhYzcwXHViMDk4IFx1YWViY1x1YzgzOFx1Yzc4OFx1YjJlNC4gXHVjYzk4XHVjNzRjXHVjNWQwIFx1YmFhOFx1YjRlMCBcdWM4MDRcdWFkNmNcdWIyOTQgXHVhZWJjXHVjODM4XHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ2MDRcdWMyMThcdWIyOTQgXHVjNzdjXHViZDgwIFx1YzgwNFx1YWQ2Y1x1Yjk3YyBcdWNmMWNcdWMxMWMgXHVjNTQ0XHViOTg0XHViMmU0XHVjNmI0IFx1ZDMyOFx1ZDEzNFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWQ2MDRcdWMyMThcdWIyOTQgXHVkNTg5XHVjNzc0XHViMDk4IFx1YzVmNFx1Yjg1YyBcdWM1ZjBcdWMxOGRcdWI0MWMgXHVjODA0XHVhZDZjXHViOTdjIFx1ZDU1OFx1YjA5OCBcdWM3NzRcdWMwYzEgXHVhY2U4XHViNzdjXHVjMTFjIFx1YzgwNFx1YWQ2Y1x1Yzc1OCBcdWMwYzFcdWQwZGNcdWI5N2MgXHViYzE0XHVhZmMwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIChcdWFlYmNcdWM4MzhcdWM3ODhcdWIyOTQgXHVjODA0XHVhZDZjIC0mZ3Q7IFx1Y2YyYywgXHVjZjFjXHVjNzg4XHViMjk0IFx1YzgwNFx1YWQ2YyAtJmd0OyBcdWIwNTQpPFwvcD5cclxuXHJcbjxwPlx1ZDYwNFx1YzIxOFx1YWMwMCBcdWI5Y2NcdWI0ZTRcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0IFx1ZDMyOFx1ZDEzNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWNkNWNcdWMxOGMgXHViYTg3IFx1YmM4OCBcdWI5Y2NcdWM1ZDAgXHVhZGY4IFx1ZDMyOFx1ZDEzNFx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNWY0XHVjNzU4IFx1ZDA2Y1x1YWUzMCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgXHViNDUwIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ2MDRcdWMyMThcdWFjMDAgXHViOWNjXHViNGU0XHViODI0XHVhY2UwIFx1ZDU1OFx1YjI5NCBcdWM1NDRcdWI5ODRcdWIyZTRcdWM2YjQgXHVkMzI4XHVkMTM0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gMVx1Yzc0MCBcdWM4MDRcdWFkNmNcdWFjMDAgXHVjZjFjXHVjODM4XHVjNzg4XHViMjk0IFx1YzBjMVx1ZDBkY1x1Yzc3NFx1YWNlMCwgMFx1Yzc0MCBcdWFlYmNcdWM4MzhcdWM3ODhcdWIyOTQgXHVjMGMxXHVkMGRjXHVjNzc0XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1ZDYwNFx1YzIxOFx1YWMwMCBcdWNkNWNcdWMxOGMgXHViYTg3IFx1YmM4OCBcdWI5Y2NcdWM1ZDAgXHVjNTQ0XHViOTg0XHViMmU0XHVjNmI0IFx1ZDMyOFx1ZDEzNFx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwic2FtcGxlX2V4cGxhaW5fMyI6Ijx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkIHRoLWNlbnRlciB0ZC1jZW50ZXJcIj5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD4wPFwvdGg+XHJcblx0XHRcdDx0aD4xPFwvdGg+XHJcblx0XHRcdDx0aD4yPFwvdGg+XHJcblx0XHRcdDx0aD4zPFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHQ8cHJlPlxyXG4wMDAwMDAwMDAwMDAwMDAwMDAwMFxyXG4wMDAwMDAwMDAwMDAwMDAwMDAwMDxcL3ByZT5cclxuXHRcdFx0PFwvdGQ+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0PHByZT5cclxuPHN0cm9uZz4xMTE8XC9zdHJvbmc+MDAwMDAwMDAwMDAwMDAwMDBcclxuMDAwMDAwMDAwMDAwMDAwMDAwMDA8XC9wcmU+XHJcblx0XHRcdDxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdDxwcmU+XHJcbjExMTAwMDxzdHJvbmc+MTxcL3N0cm9uZz4wMDAwMDAwMDAwMDAwXHJcbjAwMDAwMDxzdHJvbmc+MTxcL3N0cm9uZz4wMDAwMDAwMDAwMDAwPFwvcHJlPlxyXG5cdFx0XHQ8XC90ZD5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHQ8cHJlPlxyXG4xMTEwMDAxMDAwMDAwMDAwMDAwMFxyXG4wPHN0cm9uZz4xMTExMTAxMTxcL3N0cm9uZz4wMDAwMDAwMDAwMDxcL3ByZT5cclxuXHRcdFx0PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPjQ8XC90aD5cclxuXHRcdFx0PHRoPjU8XC90aD5cclxuXHRcdFx0PHRoPjY8XC90aD5cclxuXHRcdFx0PHRoPjc8XC90aD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdDxwcmU+XHJcbjExMTAxMTA8c3Ryb25nPjExMTE8XC9zdHJvbmc+MDAwMDAwMDAwXHJcbjAxMTExMTAxMTAwMDAwMDAwMDAwPFwvcHJlPlxyXG5cdFx0XHQ8XC90ZD5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHQ8cHJlPlxyXG4xMTEwMTEwMTExMTAwMDxzdHJvbmc+MTExMTE8XC9zdHJvbmc+MFxyXG4wMTExMTEwMTEwMDAwMDAwMDAwMDxcL3ByZT5cclxuXHRcdFx0PFwvdGQ+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0PHByZT5cclxuMTExMDExMDExMTEwMDAxPHN0cm9uZz4wPFwvc3Ryb25nPjExMTBcclxuMDExMTExMDExMDAwMDAwPHN0cm9uZz4xPFwvc3Ryb25nPjAwMDA8XC9wcmU+XHJcblx0XHRcdDxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdDxwcmU+XHJcbjExMTAxMTAxMTExMDAwMTAxPHN0cm9uZz4wPFwvc3Ryb25nPjEwXHJcbjAxMTExMTAxMTAwMDAwMDEwPHN0cm9uZz4xPFwvc3Ryb25nPjAwPFwvcHJlPlxyXG5cdFx0XHQ8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuIn0seyJwcm9ibGVtX2lkIjoiMzE1OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6ImxhbXBpY2UiLCJkZXNjcmlwdGlvbiI6IjxwPjIqTiBsaWdodCBidWxicyBhcmUgYXJyYW5nZWQgaW4gdHdvIHJvd3MgYW5kIE4gY29sdW1ucy4gRWFjaCBsaWdodCBidWxiIGNhbiBiZSBlaXRoZXIgb2ZmIG9yIG9uLCBhbmQgYWxsIGxpZ2h0cyBhcmUgaW5pdGlhbGx5IG9mZi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V2Ugd2FudCB0byB0dXJuIHNvbWUgb2YgdGhlbSBvbiBzbyB0aGF0IHRoZXkgZm9ybSBhIGJlYXV0aWZ1bCBwYXR0ZXJuLiBJbiBvbmUgc3RlcCB3ZSBjYW4gY2hhbmdlIHRoZSBzdGF0ZSBvZiBhIHNlcXVlbmNlIG9mIChvbmUgb3IgbW9yZSkgY29uc2VjdXRpdmUgbGlnaHQgYnVsYnMgaW4gdGhlIHNhbWUgcm93IG9yIGNvbHVtbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+R2l2ZW4gdGhlIGRlc2lyZWQgcGF0dGVybiwgd3JpdGUgYSBwcm9ncmFtIHRoYXQgZmluZHMgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHN0ZXBzIHJlcXVpcmVkIHRvIGZvcm0gdGhlIHBhdHRlcm4uJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhbiBpbnRlZ2VyIE4sIDEgJmxlOyBOICZsZTsgMTAsMDAwLCB0aGUgbnVtYmVyIG9mIGNvbHVtbnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyB0d28gbGluZXMgY29udGFpbnMgYSBzZXF1ZW5jZSBvZiBOIGNoYXJhY3RlcnMgcmVwcmVzZW50aW5nIHRoZSBkZXNpcmVkIGZpbmFsIHBhdHRlcm4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkNoYXJhY3RlciAmIzM5OzEmIzM5OyBpbmRpY2F0ZXMgYSBsaWdodCBidWxiIHRoYXQgc2hvdWxkIGJlIG9uIGluIHRoZSBmaW5hbCBzdGF0ZSwgd2hpbGUgdGhlIGNoYXJhY3RlciAmIzM5OzAmIzM5OyBpbmRpY2F0ZXMgYSBsaWdodCBidWxiIHRoYXQgc2hvdWxkIGJlIG9mZi4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gYSBzaW5nbGUgaW50ZWdlciAmbmRhc2g7IHRoZSBtaW5pbXVtIG51bWJlciBvZiBzdGVwcyByZXF1aXJlZC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwic2FtcGxlX2V4cGxhaW5fMyI6IjxwPlRoZSBmb2xsb3dpbmcgZmlndXJlIGlsbHVzdHJhdGVzIHRoZSBzZXZlbiBzdGVwcyBuZWVkZWQgdG8gb2J0YWluIHRoZSBwYXR0ZXJuIGdpdmVuIGluIHRoZSB0aGlyZCBleGFtcGxlOjxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZCB0aC1jZW50ZXIgdGQtY2VudGVyXCI+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+MDxcL3RoPlxyXG5cdFx0XHQ8dGg+MTxcL3RoPlxyXG5cdFx0XHQ8dGg+MjxcL3RoPlxyXG5cdFx0XHQ8dGg+MzxcL3RoPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0PHByZT5cclxuMDAwMDAwMDAwMDAwMDAwMDAwMDBcclxuMDAwMDAwMDAwMDAwMDAwMDAwMDA8XC9wcmU+XHJcblx0XHRcdDxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdDxwcmU+XHJcbjxzdHJvbmc+MTExPFwvc3Ryb25nPjAwMDAwMDAwMDAwMDAwMDAwXHJcbjAwMDAwMDAwMDAwMDAwMDAwMDAwPFwvcHJlPlxyXG5cdFx0XHQ8XC90ZD5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHQ8cHJlPlxyXG4xMTEwMDA8c3Ryb25nPjE8XC9zdHJvbmc+MDAwMDAwMDAwMDAwMFxyXG4wMDAwMDA8c3Ryb25nPjE8XC9zdHJvbmc+MDAwMDAwMDAwMDAwMDxcL3ByZT5cclxuXHRcdFx0PFwvdGQ+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0PHByZT5cclxuMTExMDAwMTAwMDAwMDAwMDAwMDBcclxuMDxzdHJvbmc+MTExMTEwMTE8XC9zdHJvbmc+MDAwMDAwMDAwMDA8XC9wcmU+XHJcblx0XHRcdDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD40PFwvdGg+XHJcblx0XHRcdDx0aD41PFwvdGg+XHJcblx0XHRcdDx0aD42PFwvdGg+XHJcblx0XHRcdDx0aD43PFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHQ8cHJlPlxyXG4xMTEwMTEwPHN0cm9uZz4xMTExPFwvc3Ryb25nPjAwMDAwMDAwMFxyXG4wMTExMTEwMTEwMDAwMDAwMDAwMDxcL3ByZT5cclxuXHRcdFx0PFwvdGQ+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0PHByZT5cclxuMTExMDExMDExMTEwMDA8c3Ryb25nPjExMTExPFwvc3Ryb25nPjBcclxuMDExMTExMDExMDAwMDAwMDAwMDA8XC9wcmU+XHJcblx0XHRcdDxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdDxwcmU+XHJcbjExMTAxMTAxMTExMDAwMTxzdHJvbmc+MDxcL3N0cm9uZz4xMTEwXHJcbjAxMTExMTAxMTAwMDAwMDxzdHJvbmc+MTxcL3N0cm9uZz4wMDAwPFwvcHJlPlxyXG5cdFx0XHQ8XC90ZD5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHQ8cHJlPlxyXG4xMTEwMTEwMTExMTAwMDEwMTxzdHJvbmc+MDxcL3N0cm9uZz4xMFxyXG4wMTExMTEwMTEwMDAwMDAxMDxzdHJvbmc+MTxcL3N0cm9uZz4wMDxcL3ByZT5cclxuXHRcdFx0PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcbiJ9XQ==