백준 온라인 저지, 그리디 / 2879번: 코딩은예쁘게 (파이썬 / 백준 골드문제)

문제

백준이는 한 작은 회사에 취직했다. 이 회사에서 백준이는 소스 코드의 뒤죽박죽인 인덴트를 고치고 있다. 인덴트는 각 줄을 탭 키를 이용해 들여 쓰는 것을 말한다. 다행히 백준이가 사용하는 편집기는 연속된 줄을 그룹으로 선택하고, 여기에서 각 줄의 앞에 탭을 추가하거나, 삭제할 수 있다. 백준이를 도와 코드의 뒤죽박죽인 인덴트를 예쁘게 고치는 방법을 생각해보자.

줄의 개수 N과 각 줄의 앞에 있는 탭의 개수와 올바른 탭의 개수가 주어진다. 이때, 한 번 편집을 할 때, 다음과 같은 명령을 수행할 수 있다.

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

위의 두 명령을 모두 수행하는 것이 하나의 편집이며, 선택된 줄의 개수와는 상관이 없다. 만약, 선택한 줄 중에 단 한 줄이라도 탭이 없을 경우에는, 탭을 삭제하는 명령을 수행할 수 없다.

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

입력

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

출력

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

제한

예제 입력 1

3
3 4 5
6 7 8

예제 출력 1

3

예제 입력 2

4
1 2 3 4
3 1 1 0

예제 출력 2

6

예제 입력 3

4
5 4 5 5
1 5 0 1

예제 출력 3

10

힌트

W3sicHJvYmxlbV9pZCI6IjI4NzkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNmNTRcdWI1MjlcdWM3NDAgXHVjNjA4XHVjMDU4XHVhYzhjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWJjMzFcdWM5MDBcdWM3NzRcdWIyOTQgXHVkNTVjIFx1Yzc5MVx1Yzc0MCBcdWQ2OGNcdWMwYWNcdWM1ZDAgXHVjZGU4XHVjOWMxXHVkNTg4XHViMmU0LiBcdWM3NzQgXHVkNjhjXHVjMGFjXHVjNWQwXHVjMTFjIFx1YmMzMVx1YzkwMFx1Yzc3NFx1YjI5NCBcdWMxOGNcdWMyYTQgXHVjZjU0XHViNGRjXHVjNzU4IFx1YjRhNFx1YzhmZFx1YmMxNVx1YzhmZFx1Yzc3OCBcdWM3NzhcdWIzNzRcdWQyYjhcdWI5N2MgXHVhY2UwXHVjZTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjNzc4XHViMzc0XHVkMmI4XHViMjk0IFx1YWMwMSBcdWM5MDRcdWM3NDQgXHVkMGVkIFx1ZDBhNFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzQgXHViNGU0XHVjNWVjIFx1YzRmMFx1YjI5NCBcdWFjODNcdWM3NDQgXHViOWQwXHVkNTVjXHViMmU0LiBcdWIyZTRcdWQ1ODlcdWQ3ODggXHViYzMxXHVjOTAwXHVjNzc0XHVhYzAwIFx1YzBhY1x1YzZhOVx1ZDU1OFx1YjI5NCBcdWQzYjhcdWM5ZDFcdWFlMzBcdWIyOTQgXHVjNWYwXHVjMThkXHViNDFjIFx1YzkwNFx1Yzc0NCBcdWFkZjhcdWI4ZjlcdWM3M2NcdWI4NWMgXHVjMTIwXHVkMGRkXHVkNTU4XHVhY2UwLCBcdWM1ZWNcdWFlMzBcdWM1ZDBcdWMxMWMgXHVhYzAxIFx1YzkwNFx1Yzc1OCBcdWM1NWVcdWM1ZDAgXHVkMGVkXHVjNzQ0IFx1Y2Q5NFx1YWMwMFx1ZDU1OFx1YWM3MFx1YjA5OCwgXHVjMGFkXHVjODFjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YmMzMVx1YzkwMFx1Yzc3NFx1Yjk3YyBcdWIzYzRcdWM2NDAgXHVjZjU0XHViNGRjXHVjNzU4IFx1YjRhNFx1YzhmZFx1YmMxNVx1YzhmZFx1Yzc3OCBcdWM3NzhcdWIzNzRcdWQyYjhcdWI5N2MgXHVjNjA4XHVjMDU4XHVhYzhjIFx1YWNlMFx1Y2U1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVjMGRkXHVhYzAxXHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcblxyXG48cD5cdWM5MDRcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWFjZmMgXHVhYzAxIFx1YzkwNFx1Yzc1OCBcdWM1NWVcdWM1ZDAgXHVjNzg4XHViMjk0IFx1ZDBlZFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM2NDAgXHVjNjJjXHViYzE0XHViOTc4IFx1ZDBlZFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1ZDU1YyBcdWJjODggXHVkM2I4XHVjOWQxXHVjNzQ0IFx1ZDU2MCBcdWI1NGMsIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHViYTg1XHViODM5XHVjNzQ0IFx1YzIxOFx1ZDU4OVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YzVmMFx1YzE4ZFx1YjQxYyBcdWM5MDRcdWM3NDQgXHVhZGY4XHViOGY5XHVjNzNjXHViODVjIFx1YzEyMFx1ZDBkZFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjMTIwXHVkMGRkXHViNDFjIFx1YzkwNFx1Yzc1OCBcdWM1NWVcdWM1ZDAgXHVkMGVkIDFcdWFjMWNcdWI5N2MgXHVjZDk0XHVhYzAwXHVkNTU4XHVhYzcwXHViMDk4IFx1YzBhZFx1YzgxY1x1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM3MDRcdWM3NTggXHViNDUwIFx1YmE4NVx1YjgzOVx1Yzc0NCBcdWJhYThcdWI0NTAgXHVjMjE4XHVkNTg5XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NCBcdWQ1NThcdWIwOThcdWM3NTggXHVkM2I4XHVjOWQxXHVjNzc0XHViYTcwLCBcdWMxMjBcdWQwZGRcdWI0MWMgXHVjOTA0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YzY0MFx1YjI5NCBcdWMwYzFcdWFkMDBcdWM3NzQgXHVjNWM2XHViMmU0LiZuYnNwO1x1YjljY1x1YzU3ZCwgXHVjMTIwXHVkMGRkXHVkNTVjIFx1YzkwNCBcdWM5MTFcdWM1ZDAgXHViMmU4IFx1ZDU1YyBcdWM5MDRcdWM3NzRcdWI3N2NcdWIzYzQgXHVkMGVkXHVjNzc0IFx1YzVjNlx1Yzc0NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQsIFx1ZDBlZFx1Yzc0NCBcdWMwYWRcdWM4MWNcdWQ1NThcdWIyOTQgXHViYTg1XHViODM5XHVjNzQ0IFx1YzIxOFx1ZDU4OVx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJjMzFcdWM5MDBcdWM3NzRcdWFjMDAgXHViYTg3IFx1YmM4OCBcdWQzYjhcdWM5ZDEgXHViOWNjXHVjNWQwIFx1Y2Y1NFx1YjRkY1x1Yzc1OCBcdWM3NzhcdWIzNzRcdWQyYjhcdWI5N2MgXHVjNjJjXHViYzE0XHViOTc0XHVhYzhjIFx1YWNlMFx1Y2U2MCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWM3NzRcdWI1NGMsIFx1ZDNiOFx1YzlkMSBcdWQ2OGNcdWMyMThcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzkwNFx1Yzc1OCBcdWFjMWNcdWMyMTggTigxICZsZTsgTiAmbGU7IDEsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNjA0XHVjN2FjIFx1YzkwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVkMGVkXHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIDFcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDBlZFx1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgMFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCA4MFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC4gXHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjOTA0XHVjNzU4IFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWQwZWRcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gMVx1YmM4OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVjNzc0IFx1YWMxMlx1YjNjNCAwXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDgwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjZjU0XHViNGRjXHVjNzU4IFx1Yzc3OFx1YjM3NFx1ZDJiOFx1Yjk3YyBcdWM2MmNcdWJjMTRcdWI5NzRcdWFjOGMgXHVhY2UwXHVjZTU4XHViMjk0IFx1ZDNiOFx1YzlkMSBcdWQ2OGNcdWMyMThcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyODc5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVEFCT1ZJIiwiZGVzY3JpcHRpb24iOiI8cD5adm9ua2VjIGlzIHlldCBhbm90aGVyIHByb2dyYW1tZXIgZW1wbG95ZWQgaW4gYSBzbWFsbCBjb21wYW55LiBFdmVyeSBkYXkgaGUgaGFzIHRvIHJlZmFjdG9yIG9uZSBmaWxlIG9mIHNvdXJjZSBjb2RlLiBNdWNoIHRvIGhpcyBkaXNtYXksIHRoZSBzb3VyY2UgaXMgdXN1YWxseSBmYXIgZnJvbSBiZWluZyBjbGVhciBhbmQgdGlkeS4gSGUgaXMgZXNwZWNpYWxseSBib3RoZXJlZCBieSB1bmV2ZW4gaW5kZW50YXRpb24sIGkuZS4gdGhlIG51bWJlciBvZiB0YWJ1bGF0b3JzICh0YWJzKSBpbmRlbnRpbmcgZWFjaCBsaW5lLiBGb3J0dW5hdGVseSwgaGlzIGVkaXRvciBoYXMgYSBjb21tYW5kIHRvIHNlbGVjdCBhIGdyb3VwIG9mIGNvbnNlY3V0aXZlIGxpbmVzIGFuZCBhZGQgb3IgZGVsZXRlIGEgY2hhcmFjdGVyIGZyb20gdGhlIHN0YXJ0IG9mIGVhY2ggb25lLiBIZWxwIFp2b25rZWMgdGlkeSB1cCB0aGUgY29kZSBhcyBxdWlja2x5IGFzIHBvc3NpYmxlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIGdpdmVuIHRoZSBudW1iZXIgb2YgbGluZXMgTiwgYSBzZXF1ZW5jZSBzcGVjaWZ5aW5nIHRoZSBjdXJyZW50IG51bWJlciBvZiB0YWJzIGF0IHRoZSBzdGFydCBvZiBlYWNoIGxpbmUsIGFuZCBhIHNlcXVlbmNlIHNwZWNpZnlpbmcgdGhlIHJlcXVpcmVkIG51bWJlciBvZiB0YWJzIGF0IHRoZSBzdGFydCBvZiBlYWNoIGxpbmUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlp2b25rZWMgY2FuIGV4ZWN1dGUgYW55IG51bWJlciBvZiBjb21tYW5kcyBjb25zaXN0aW5nIG9mOiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnNlbGVjdGluZyBhbnkgbnVtYmVyIG9mIGNvbnNlY3V0aXZlIGxpbmVzJm5ic3A7PFwvbGk+XHJcblx0PGxpPmFkZGluZyBvciBkZWxldGluZyBhIHNpbmdsZSB0YWIgdG9cL2Zyb20gdGhlIGZyb250IG9mIGVhY2ggb2YgdGhlIHNlbGVjdGVkIGxpbmVzJm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+VGhlIHR3byBhY3Rpb25zIGFib3ZlIGNvbXByaXNlIGEgc2luZ2xlIGNvbW1hbmQsIHJlZ2FyZGxlc3Mgb2YgdGhlIG51bWJlciBvZiBzZWxlY3RlZCBsaW5lcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SXQgc2hvdWxkIGJlIG5vdGVkIHRoYXQgaXQgaXMgZm9yYmlkZGVuIHRvIGRlbGV0ZSBtb3JlIHRhYnMgZnJvbSBhIGxpbmUgdGhhbiBhcmUgYWN0dWFsbHkgcHJlc2VudCBhdCB0aGUgc3RhcnQgb2YgYSBsaW5lLCBhcyB0aGUgZWRpdG9yIHdvdWxkIHN0YXJ0IGRlbGV0aW5nIGNoYXJhY3RlcnMgb3RoZXIgdGhhbiB0YWJzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIGFza2VkIHRvIGNhbGN1bGF0ZSB0aGUgbWluaW11bSBudW1iZXIgb2YgY29tbWFuZHMgcmVxdWlyZWQgdG8gdGlkeSB1cCB0aGUgY29kZS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgcG9zaXRpdmUgaW50ZWdlciBOIChOICZsZTsgMTAwMCkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyBhIHNlcXVlbmNlIG9mIE4gaW50ZWdlcnMgUDxzdWI+aTxcL3N1Yj4gKDAgJmxlOyBQPHN1Yj5pPFwvc3ViPiAmbGU7IDgwKSwgc3BlY2lmeWluZyB0aGUgbnVtYmVyIG9mIHRhYnMgYXQgdGhlIHN0YXJ0IG9mIGktdGggbGluZSBiZWZvcmUgYW55IGVkaXRpbmcuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSB0aGlyZCBsaW5lIGNvbnRhaW5zIGEgc2VxdWVuY2Ugb2YgTiBpbnRlZ2VycyBLPHN1Yj5pPFwvc3ViPiAoMCAmbGU7IEs8c3ViPmk8XC9zdWI+ICZsZTsgODApLCBzcGVjaWZ5aW5nIHRoZSBudW1iZXIgb2YgdGFicyB0aGF0IFp2b25rZWMgd291bGQgbGlrZSBhdCB0aGUgc3RhcnQgb2YgaS10aCBsaW5lLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIHJlcXVpcmVkIG51bWJlciwgYXMgc3BlY2lmaWVkIGluIHRoZSBwcm9ibGVtIHN0YXRlbWVudC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

접근 방법

- 현재 줄에 있는 탭과 올바른 탭을 비교하며 현재 상태에 따라 편집횟수를 저장한다.
- 1. 증가상태나 삭제상태에서 현재 줄에 있는 탭의 개수와 올바른 탭의 개수가 같다면 패스 상태(0)로 변환 후 패스한다.
- 2. 여태 바꾸지 않았거나 증가상태라면 현재 줄에 있는 탭의 개수가 올바른 탭의 개수보다 크다면 개수를 하나 줄이고, 편집횟수를 하나 늘린다음 삭제 상태(1)로 변경한다.
- 2-1. 삭제 상태에서 현재 줄에 있는 탭의 개수가 올바른 탭의 개수보다 크다면 개수를 하나 줄이고 패스한다.
- 3.여태 바꾸지 않았거나 삭제상태라면 현재 줄에 있는 탭의 개수가 올바른 탭의 개수보다 작다면 개수를 하나 늘리고, 편집횟수를 하나 늘린다음 증가 상태(2)로 변경한다.
- 3-1. 증가 상태에서 현재 줄에 있는 탭의 개수가 올바른 탭의 개수보다 작다면 개수를 하나 늘리고 패스한다.
- 모든 탐색이 끝나면 편집 횟수를 출력하고 종료한다.

코드

# https://www.acmicpc.net/problem/2879
# 접근방법
# 현재 줄에 있는 탭과 올바른 탭을 비교하며 현재 상태에 따라 편집횟수를 저장한다.
# 1. 증가상태나 삭제상태에서 현재 줄에 있는 탭의 개수와 올바른 탭의 개수가 같다면 패스 상태(0)로 변환 후 패스한다.
# 2. 여태 바꾸지 않았거나 증가상태라면 현재 줄에 있는 탭의 개수가 올바른 탭의 개수보다 크다면 개수를 하나 줄이고, 편집횟수를 하나 늘린다음 삭제 상태(1)로 변경한다.
# 2-1. 삭제 상태에서 현재 줄에 있는 탭의 개수가 올바른 탭의 개수보다 크다면 개수를 하나 줄이고 패스한다.
# 3.여태 바꾸지 않았거나 삭제상태라면 현재 줄에 있는 탭의 개수가 올바른 탭의 개수보다 작다면 개수를 하나 늘리고, 편집횟수를 하나 늘린다음 증가 상태(2)로 변경한다.
# 3-1. 증가 상태에서 현재 줄에 있는 탭의 개수가 올바른 탭의 개수보다 작다면 개수를 하나 늘리고 패스한다.
# 모든 탐색이 끝나면 편집 횟수를 출력하고 종료한다.


n = int(input())
now_tab = list(map(int, input().split()))
correct_tab = list(map(int, input().split()))

count = 0
condition = [0, 1, 2]
check = 0
while now_tab != correct_tab:
    for i in range(n):
        if now_tab[i] == correct_tab[i]:
            check = 0
        elif now_tab[i] > correct_tab[i]:
            if check != 1:
                count += 1
                now_tab[i] -= 1
                check = 1
            else:
                now_tab[i] -= 1
        else:
            if check != 2:
                count += 1
                now_tab[i] += 1
                check = 2
            else:
                now_tab[i] += 1
    check = 0

print(count)