시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1012 362 265 41.022%

문제

백준이는 한 작은 회사에 취직했다. 이 회사에서 백준이는 소스 코드의 뒤죽박죽인 인덴트를 고치고 있다. 인덴트는 각 줄을 탭 키를 이용해 들여 쓰는 것을 말한다.

다행히 백준이가 사용하는 편집기는 연속된 줄을 그룹으로 선택하고, 여기에서 각 줄의 앞에 탭을 추가하거나, 삭제할 수 있다.

백준이를 도와 코드의 뒤죽박죽인 인덴트를 예쁘게 고치는 방법을 생각해보자.

줄의 개수 N과 각 줄의 앞에 있는 탭의 개수와 올바른 탭의 개수가 주어진다.

이 때, 한 번 편집을 할 때, 다음과 같은 명령을 수행할 수 있다.

  • 연속된 줄을 그룹으로 선택한다.
  • 선택된 줄의 앞에 탭 1개를 추가하거나 삭제한다.

위의 두 명령은 각각 선택된 줄의 개수와 상관없이 한 번의 편집이다.

만약, 선택한 줄 중에 단 한 줄이라도 탭이 없을 경우에는, 탭을 삭제하는 명령을 수행할 수 없다.

백준이가 몇 번 편집 만에 코드의 인덴트를 올바르게 고칠 수 있는지 구하는 프로그램을 작성하시오. 이 때, 편집 회수의 최소값을 구해야 한다.

입력

 

첫째 줄에 줄의 개수 N(N<=1,000)이 주어진다. 둘째 줄에는 현재 줄에 있는 탭의 개수가 주어지며, 1번째 줄부터 순서대로 주어진다. 탭의 개수는 0보다 크거나 같고, 80보다 작거나 같은 정수이다. 셋째 줄에는 각 줄의 올바른 탭의 개수가 주어진다. 1번째 줄부터 순서대로 주어지며, 이 값도 0보다 크거나 같고, 80보다 작거나 같은 정수이다.

 

출력

첫째 줄에 코드의 인덴트를 올바르게 고치는 편집 회수의 최소값을 출력한다.

예제 입력 1

4
1 2 3 4
3 1 1 0

예제 출력 1

6
W3sicHJvYmxlbV9pZCI6IjI4NzkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNmNTRcdWI1MjlcdWM3NDAgXHVjNjA4XHVjMDU4XHVhYzhjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWJjMzFcdWM5MDBcdWM3NzRcdWIyOTQgXHVkNTVjIFx1Yzc5MVx1Yzc0MCBcdWQ2OGNcdWMwYWNcdWM1ZDAgXHVjZGU4XHVjOWMxXHVkNTg4XHViMmU0LiBcdWM3NzQgXHVkNjhjXHVjMGFjXHVjNWQwXHVjMTFjIFx1YmMzMVx1YzkwMFx1Yzc3NFx1YjI5NCBcdWMxOGNcdWMyYTQgXHVjZjU0XHViNGRjXHVjNzU4IFx1YjRhNFx1YzhmZFx1YmMxNVx1YzhmZFx1Yzc3OCBcdWM3NzhcdWIzNzRcdWQyYjhcdWI5N2MgXHVhY2UwXHVjZTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjNzc4XHViMzc0XHVkMmI4XHViMjk0IFx1YWMwMSBcdWM5MDRcdWM3NDQgXHVkMGVkIFx1ZDBhNFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzQgXHViNGU0XHVjNWVjIFx1YzRmMFx1YjI5NCBcdWFjODNcdWM3NDQgXHViOWQwXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWQ1ODlcdWQ3ODggXHViYzMxXHVjOTAwXHVjNzc0XHVhYzAwIFx1YzBhY1x1YzZhOVx1ZDU1OFx1YjI5NCBcdWQzYjhcdWM5ZDFcdWFlMzBcdWIyOTQgXHVjNWYwXHVjMThkXHViNDFjIFx1YzkwNFx1Yzc0NCBcdWFkZjhcdWI4ZjlcdWM3M2NcdWI4NWMgXHVjMTIwXHVkMGRkXHVkNTU4XHVhY2UwLCBcdWM1ZWNcdWFlMzBcdWM1ZDBcdWMxMWMgXHVhYzAxIFx1YzkwNFx1Yzc1OCBcdWM1NWVcdWM1ZDAgXHVkMGVkXHVjNzQ0IFx1Y2Q5NFx1YWMwMFx1ZDU1OFx1YWM3MFx1YjA5OCwgXHVjMGFkXHVjODFjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmMzMVx1YzkwMFx1Yzc3NFx1Yjk3YyBcdWIzYzRcdWM2NDAgXHVjZjU0XHViNGRjXHVjNzU4IFx1YjRhNFx1YzhmZFx1YmMxNVx1YzhmZFx1Yzc3OCBcdWM3NzhcdWIzNzRcdWQyYjhcdWI5N2MgXHVjNjA4XHVjMDU4XHVhYzhjIFx1YWNlMFx1Y2U1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVjMGRkXHVhYzAxXHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcblxyXG48cD5cdWM5MDRcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWFjZmMgXHVhYzAxIFx1YzkwNFx1Yzc1OCBcdWM1NWVcdWM1ZDAgXHVjNzg4XHViMjk0IFx1ZDBlZFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM2NDAgXHVjNjJjXHViYzE0XHViOTc4IFx1ZDBlZFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHViNTRjLCBcdWQ1NWMgXHViYzg4IFx1ZDNiOFx1YzlkMVx1Yzc0NCBcdWQ1NjAgXHViNTRjLCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YmE4NVx1YjgzOVx1Yzc0NCBcdWMyMThcdWQ1ODlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWM1ZjBcdWMxOGRcdWI0MWMgXHVjOTA0XHVjNzQ0IFx1YWRmOFx1YjhmOVx1YzczY1x1Yjg1YyBcdWMxMjBcdWQwZGRcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzEyMFx1ZDBkZFx1YjQxYyBcdWM5MDRcdWM3NTggXHVjNTVlXHVjNWQwIFx1ZDBlZCAxXHVhYzFjXHViOTdjIFx1Y2Q5NFx1YWMwMFx1ZDU1OFx1YWM3MFx1YjA5OCBcdWMwYWRcdWM4MWNcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNzA0XHVjNzU4IFx1YjQ1MCBcdWJhODVcdWI4MzlcdWM3NDAmbmJzcDtcdWFjMDFcdWFjMDEgXHVjMTIwXHVkMGRkXHViNDFjIFx1YzkwNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM2NDAgXHVjMGMxXHVhZDAwXHVjNWM2XHVjNzc0IFx1ZDU1YyBcdWJjODhcdWM3NTggXHVkM2I4XHVjOWQxXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5Y2NcdWM1N2QsIFx1YzEyMFx1ZDBkZFx1ZDU1YyBcdWM5MDQgXHVjOTExXHVjNWQwIFx1YjJlOCBcdWQ1NWMgXHVjOTA0XHVjNzc0XHViNzdjXHViM2M0IFx1ZDBlZFx1Yzc3NCBcdWM1YzZcdWM3NDQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0LCBcdWQwZWRcdWM3NDQgXHVjMGFkXHVjODFjXHVkNTU4XHViMjk0IFx1YmE4NVx1YjgzOVx1Yzc0NCBcdWMyMThcdWQ1ODlcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYzMxXHVjOTAwXHVjNzc0XHVhYzAwIFx1YmE4NyBcdWJjODggXHVkM2I4XHVjOWQxIFx1YjljY1x1YzVkMCBcdWNmNTRcdWI0ZGNcdWM3NTggXHVjNzc4XHViMzc0XHVkMmI4XHViOTdjIFx1YzYyY1x1YmMxNFx1Yjk3NFx1YWM4YyBcdWFjZTBcdWNlNjAgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjNzc0IFx1YjU0YywgXHVkM2I4XHVjOWQxIFx1ZDY4Y1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzkwNFx1Yzc1OCBcdWFjMWNcdWMyMTggTihOJmx0Oz0xLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDYwNFx1YzdhYyBcdWM5MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1ZDBlZFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCAxXHViYzg4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQwZWRcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IDBcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgODBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuIFx1YzE0Ylx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YzkwNFx1Yzc1OCBcdWM2MmNcdWJjMTRcdWI5NzggXHVkMGVkXHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIDFcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1Yzc3NCBcdWFjMTJcdWIzYzQgMFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCA4MFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNmNTRcdWI0ZGNcdWM3NTggXHVjNzc4XHViMzc0XHVkMmI4XHViOTdjIFx1YzYyY1x1YmMxNFx1Yjk3NFx1YWM4YyBcdWFjZTBcdWNlNThcdWIyOTQgXHVkM2I4XHVjOWQxIFx1ZDY4Y1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI4NzkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUQUJPVkkiLCJkZXNjcmlwdGlvbiI6IjxwPlp2b25rZWMgaXMgeWV0IGFub3RoZXIgcHJvZ3JhbW1lciBlbXBsb3llZCBpbiBhIHNtYWxsIGNvbXBhbnkuIEV2ZXJ5IGRheSBoZSBoYXMgdG8gcmVmYWN0b3Igb25lIGZpbGUgb2Ygc291cmNlIGNvZGUuIE11Y2ggdG8gaGlzIGRpc21heSwgdGhlIHNvdXJjZSBpcyB1c3VhbGx5IGZhciBmcm9tIGJlaW5nIGNsZWFyIGFuZCB0aWR5LiBIZSBpcyBlc3BlY2lhbGx5IGJvdGhlcmVkIGJ5IHVuZXZlbiBpbmRlbnRhdGlvbiwgaS5lLiB0aGUgbnVtYmVyIG9mIHRhYnVsYXRvcnMgKHRhYnMpIGluZGVudGluZyBlYWNoIGxpbmUuIEZvcnR1bmF0ZWx5LCBoaXMgZWRpdG9yIGhhcyBhIGNvbW1hbmQgdG8gc2VsZWN0IGEgZ3JvdXAgb2YgY29uc2VjdXRpdmUgbGluZXMgYW5kIGFkZCBvciBkZWxldGUgYSBjaGFyYWN0ZXIgZnJvbSB0aGUgc3RhcnQgb2YgZWFjaCBvbmUuIEhlbHAgWnZvbmtlYyB0aWR5IHVwIHRoZSBjb2RlIGFzIHF1aWNrbHkgYXMgcG9zc2libGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPllvdSBhcmUgZ2l2ZW4gdGhlIG51bWJlciBvZiBsaW5lcyBOLCBhIHNlcXVlbmNlIHNwZWNpZnlpbmcgdGhlIGN1cnJlbnQgbnVtYmVyIG9mIHRhYnMgYXQgdGhlIHN0YXJ0IG9mIGVhY2ggbGluZSwgYW5kIGEgc2VxdWVuY2Ugc3BlY2lmeWluZyB0aGUgcmVxdWlyZWQgbnVtYmVyIG9mIHRhYnMgYXQgdGhlIHN0YXJ0IG9mIGVhY2ggbGluZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+WnZvbmtlYyBjYW4gZXhlY3V0ZSBhbnkgbnVtYmVyIG9mIGNvbW1hbmRzIGNvbnNpc3Rpbmcgb2Y6Jm5ic3A7PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+c2VsZWN0aW5nIGFueSBudW1iZXIgb2YgY29uc2VjdXRpdmUgbGluZXMmbmJzcDs8XC9saT5cclxuXHQ8bGk+YWRkaW5nIG9yIGRlbGV0aW5nIGEgc2luZ2xlIHRhYiB0b1wvZnJvbSB0aGUgZnJvbnQgb2YgZWFjaCBvZiB0aGUgc2VsZWN0ZWQgbGluZXMmbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGUgdHdvIGFjdGlvbnMgYWJvdmUgY29tcHJpc2UgYSBzaW5nbGUgY29tbWFuZCwgcmVnYXJkbGVzcyBvZiB0aGUgbnVtYmVyIG9mIHNlbGVjdGVkIGxpbmVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5JdCBzaG91bGQgYmUgbm90ZWQgdGhhdCBpdCBpcyBmb3JiaWRkZW4gdG8gZGVsZXRlIG1vcmUgdGFicyBmcm9tIGEgbGluZSB0aGFuIGFyZSBhY3R1YWxseSBwcmVzZW50IGF0IHRoZSBzdGFydCBvZiBhIGxpbmUsIGFzIHRoZSBlZGl0b3Igd291bGQgc3RhcnQgZGVsZXRpbmcgY2hhcmFjdGVycyBvdGhlciB0aGFuIHRhYnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPllvdSBhcmUgYXNrZWQgdG8gY2FsY3VsYXRlIHRoZSBtaW5pbXVtIG51bWJlciBvZiBjb21tYW5kcyByZXF1aXJlZCB0byB0aWR5IHVwIHRoZSBjb2RlLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBwb3NpdGl2ZSBpbnRlZ2VyIE4gKE4gJmxlOyAxMDAwKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIGEgc2VxdWVuY2Ugb2YgTiBpbnRlZ2VycyBQPHN1Yj5pPFwvc3ViPiAoMCAmbGU7IFA8c3ViPmk8XC9zdWI+ICZsZTsgODApLCBzcGVjaWZ5aW5nIHRoZSBudW1iZXIgb2YgdGFicyBhdCB0aGUgc3RhcnQgb2YgaS10aCBsaW5lIGJlZm9yZSBhbnkgZWRpdGluZy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHRoaXJkIGxpbmUgY29udGFpbnMgYSBzZXF1ZW5jZSBvZiBOIGludGVnZXJzIEs8c3ViPmk8XC9zdWI+ICgwICZsZTsgSzxzdWI+aTxcL3N1Yj4gJmxlOyA4MCksIHNwZWNpZnlpbmcgdGhlIG51bWJlciBvZiB0YWJzIHRoYXQgWnZvbmtlYyB3b3VsZCBsaWtlIGF0IHRoZSBzdGFydCBvZiBpLXRoIGxpbmUuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgcmVxdWlyZWQgbnVtYmVyLCBhcyBzcGVjaWZpZWQgaW4gdGhlIHByb2JsZW0gc3RhdGVtZW50LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #1 5번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013