시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1584 698 650 46.395%

문제

학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어의 점수는 레벨을 클리어하면서 얻은 점수의 합으로, 이 점수를 바탕으로 온라인 순위를 매긴다. 동준이는 레벨을 난이도 순으로 배치했다. 하지만, 실수로 쉬운 레벨이 어려운 레벨보다 점수를 많이 받는 경우를 만들었다.

이 문제를 해결하기 위해 동준이는 특정 레벨의 점수를 감소시키려고 한다. 이렇게해서 각 레벨을 클리어할 때 주는 점수가 증가하게 만드려고 한다.

각 레벨을 클리어할 때 얻는 점수가 주어졌을 때, 몇 번 감소시키면 되는지 구하는 프로그램을 작성하시오. 점수는 항상 양수이어야 하고, 1만큼 감소시키는 것이 1번이다. 항상 답이 존재하는 경우만 주어진다. 정답이 여러 가지인 경우에는 점수를 내리는 것을 최소한으로 하는 방법을 찾아야 한다.

입력

첫째 줄에 레벨의 수 N이 주어진다. (1 ≤ N ≤ 100) 다음 N개 줄에는 각 레벨을 클리어하면 얻는 점수가 첫 번째 레벨부터 마지막 레벨까지 순서대로 주어진다. 점수는 20,000보다 작은 양의 정수이다.

출력

첫째 줄에 점수를 몇 번 감소시키면 되는지 출력한다.

예제 입력 1

4
5
3
7
5

예제 출력 1

6
W3sicHJvYmxlbV9pZCI6IjI4NDciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjOGNcdWM3ODRcdWM3NDQgXHViOWNjXHViNGUwIFx1YjNkOVx1YzkwMFx1Yzc3NCIsImRlc2NyaXB0aW9uIjoiPHA+XHVkNTU5XHVhZDUwXHVjNWQwXHVjMTFjIFx1YWRmOFx1Yjc5OFx1ZDUzZFx1YzJhNCBcdWMyMThcdWM1YzVcdWM3NDQgXHViNGU0XHVjNzQwIFx1YjNkOVx1YzkwMFx1Yzc3NFx1YjI5NCBcdWMyMThcdWM1YzVcdWMyZGNcdWFjMDRcdWM1ZDAgXHViNGU0XHVjNzQwIFx1YjBiNFx1YzZhOVx1Yzc0NCBcdWJjMTRcdWQwZDVcdWM3M2NcdWI4NWMgXHVjMmE0XHViOWM4XHVkMmI4XHVkM2YwIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTQuIFx1YWM4Y1x1Yzc4NFx1YzVkMFx1YjI5NCBcdWNkMWQgTlx1YWMxY1x1Yzc1OCBcdWI4MDhcdWJjYThcdWM3NzQgXHVjNzg4XHVhY2UwLCBcdWFjMDEgXHViODA4XHViY2E4XHVjNzQ0IFx1ZDA3NFx1YjlhY1x1YzViNFx1ZDU2MCBcdWI1NGMgXHViOWM4XHViMmU0IFx1YzgxMFx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1Yzc1OCBcdWM4MTBcdWMyMThcdWIyOTQgXHViODA4XHViY2E4XHVjNzQ0IFx1ZDA3NFx1YjlhY1x1YzViNFx1ZDU1OFx1YmE3NFx1YzExYyBcdWM1YmJcdWM3NDAgXHVjODEwXHVjMjE4XHVjNzU4IFx1ZDU2OVx1YzczY1x1Yjg1YywgXHVjNzc0IFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWJjMTRcdWQwZDVcdWM3M2NcdWI4NWMgXHVjNjI4XHViNzdjXHVjNzc4IFx1YzIxY1x1YzcwNFx1Yjk3YyBcdWI5ZTRcdWFlMzRcdWIyZTQuIFx1YjNkOVx1YzkwMFx1Yzc3NFx1YjI5NCBcdWI4MDhcdWJjYThcdWM3NDQgXHViMDljXHVjNzc0XHViM2M0IFx1YzIxY1x1YzczY1x1Yjg1YyBcdWJjMzBcdWNlNThcdWQ1ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVjMmU0XHVjMjE4XHViODVjIFx1YzI2Y1x1YzZiNCBcdWI4MDhcdWJjYThcdWM3NzQgXHVjNWI0XHViODI0XHVjNmI0IFx1YjgwOFx1YmNhOFx1YmNmNFx1YjJlNCBcdWM4MTBcdWMyMThcdWI5N2MgXHViOWNlXHVjNzc0IFx1YmMxYlx1YjI5NCBcdWFjYmRcdWM2YjBcdWI5N2MgXHViOWNjXHViNGU0XHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHViYjM4XHVjODFjXHViOTdjIFx1ZDU3NFx1YWNiMFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHViM2Q5XHVjOTAwXHVjNzc0XHViMjk0IFx1ZDJiOVx1YzgxNSBcdWI4MDhcdWJjYThcdWM3NTggXHVjODEwXHVjMjE4XHViOTdjIFx1YWMxMFx1YzE4Y1x1YzJkY1x1ZDBhNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjgwN1x1YWM4Y1x1ZDU3NFx1YzExYyBcdWFjMDEgXHViODA4XHViY2E4XHVjNzQ0IFx1ZDA3NFx1YjlhY1x1YzViNFx1ZDU2MCBcdWI1NGMgXHVjOGZjXHViMjk0IFx1YzgxMFx1YzIxOFx1YWMwMCBcdWM5OWRcdWFjMDBcdWQ1NThcdWFjOGMgXHViOWNjXHViNGRjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1YjgwOFx1YmNhOFx1Yzc0NCBcdWQwNzRcdWI5YWNcdWM1YjRcdWQ1NjAgXHViNTRjIFx1YzViYlx1YjI5NCBcdWM4MTBcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViYTg3IFx1YmM4OCBcdWFjMTBcdWMxOGNcdWMyZGNcdWQwYTRcdWJhNzQgXHViNDE4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWM4MTBcdWMyMThcdWIyOTQgXHVkNTZkXHVjMGMxIFx1YzU5MVx1YzIxOFx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NThcdWFjZTAsIDFcdWI5Y2NcdWQwN2MgXHVhYzEwXHVjMThjXHVjMmRjXHVkMGE0XHViMjk0IFx1YWM4M1x1Yzc3NCAxXHViYzg4XHVjNzc0XHViMmU0LiBcdWQ1NmRcdWMwYzEgXHViMmY1XHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWI5Y2MgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM4MTVcdWIyZjVcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQmbmJzcDs8c3BhbiBzdHlsZT1cImNvbG9yOnJnYig4NSwgODUsIDg1KTsgZm9udC1mYW1pbHk6b3BlbiBzYW5zLGhlbHZldGljYSBuZXVlLGhlbHZldGljYSxhcmlhbCxhcHBsZSBzZCBnb3RoaWMgbmVvLG5vdG8gc2FucyBjamsga3Isbm90byBzYW5zIGtyLFx1YjA5OFx1YjIxNFx1YmMxNFx1Yjk3OFx1YWNlMFx1YjUxNSxcdWIwOThcdWIyMTRcdWFjZTBcdWI1MTUsbmFudW1nb3RoaWMsXHViOWQxXHVjNzQwXHVhY2UwXHViNTE1LG1hbGd1biBnb3RoaWMsbmFudW0gZ290aGljLHNhbnMtc2VyaWZcIj5cdWM4MTBcdWMyMThcdWI5N2MgXHViMGI0XHViOWFjXHViMjk0IFx1YWM4M1x1Yzc0NCBcdWNkNWNcdWMxOGNcdWQ1NWNcdWM3M2NcdWI4NWMgXHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWNjM2VcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3NwYW4+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjgwOFx1YmNhOFx1Yzc1OCBcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEwMCkgXHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWI4MDhcdWJjYThcdWM3NDQgXHVkMDc0XHViOWFjXHVjNWI0XHVkNTU4XHViYTc0IFx1YzViYlx1YjI5NCBcdWM4MTBcdWMyMThcdWFjMDAgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWI4MDhcdWJjYThcdWJkODBcdWQxMzAgXHViOWM4XHVjOWMwXHViOWM5IFx1YjgwOFx1YmNhOFx1YWU0Y1x1YzljMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM4MTBcdWMyMThcdWIyOTQgMjAsMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1Yzc0MCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODEwXHVjMjE4XHViOTdjIFx1YmE4NyBcdWJjODggXHVhYzEwXHVjMThjXHVjMmRjXHVkMGE0XHViYTc0IFx1YjQxOFx1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjg0NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJBWklORSIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gaGFzIGRldmVsb3BlZCBoaXMgb3duIHZpZGVvIGdhbWUuIFRoZSBnYW1lIGhhcyBOIGxldmVscyBhbmQgZWFjaCBzdWNjZXNzZnVsbHkgY29tcGxldGVkIGxldmVsIGlzIHdvcnRoIGEgY2VydGFpbiBudW1iZXIgb2YgcG9pbnRzLCB3aGljaCBhZGQgdXAgdG8gdGhlIHBsYXllciZyc3F1bztzIHRvdGFsIHNjb3JlIG9uIGFuIG9ubGluZSByYW5rIGxpc3Qgb2YgYWxsIHBsYXllcnMuIE1pcmtvIGhhcyBvcmRlcmVkIGhpcyBsZXZlbHMgYnkgZGlmZmljdWx0eSBmcm9tIHRoZSBlYXNpZXN0IHRvIHRoZSBtb3N0IGRpZmZpY3VsdCwgYnV0IGhlIGhhcyBtYWRlIGEgbWlzdGFrZSBhbmQgbWFkZSBzb21lIGRpZmZpY3VsdCBsZXZlbHMgd29ydGggbGVzcyBwb2ludHMgdGhhbiBzb21lIG9mIHRoZSBlYXNpZXIgb25lcy48XC9wPlxyXG5cclxuPHA+VG8gb3ZlcmNvbWUgdGhpcyBwcm9ibGVtLCBNaXJrbyBoYXMgZGVjaWRlZCB0byByZWR1Y2UgdGhlIG51bWJlciBvZiBwb2ludHMgZm9yIGNlcnRhaW4gbGV2ZWxzIHdpdGggdGhlIGdvYWwgb2YgbWFraW5nIHRoZSBwb2ludCBzZXF1ZW5jZSBzdHJpY3RseSBpbmNyZWFzaW5nIChzbyBpbiB0aGUgZW5kIGVhc2llciBsZXZlbHMgYXJlIHdvcnRoIGxlc3MgcG9pbnRzIHRoYW4gdGhlIGRpZmZpY3VsdCBvbmVzKS48XC9wPlxyXG5cclxuPHA+SGVscCBNaXJrbyBmaXggaGlzIHZpZGVvIGdhbWUgaW4gc3VjaCBhIHdheSB0aGF0IHRoZSB0b3RhbCBudW1iZXIgb2YgcG9pbnRzIHJlZHVjZWQgaXMgbWluaW1hbC4gRmluYWwgcG9pbnRzIGhhdmUgdG8gYmUgcG9zaXRpdmUuIFlvdSBjYW4gYXNzdW1lIHRoYXQgYSBzb2x1dGlvbiBleGlzdHMgZm9yIGVhY2ggdGVzdCBjYXNlPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBvbmUgcG9zaXRpdmUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDEwMCksIHRoZSBudW1iZXIgb2YgbGV2ZWxzLjxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBOIGxpbmVzIGNvbnRhaW4gcG9zaXRpdmUgaW50ZWdlcnMgbGVzcyB0aGFuIDIwIDAwMCwgdGhlIG51bWJlciBvZiBwb2ludHMgdGhhdCBNaXJrbyBoYXMgYXNzb2NpYXRlZCB3aXRoIGVhY2ggbGV2ZWwsIGZyb20gdGhlIGZpcnN0IHRvIHRoZSBsYXN0IGxldmVsLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gb25lIG51bWJlciAtIHRoZSBtaW5pbXVtIHRvdGFsIG51bWJlciBvZiBwb2ludHMgTWlya28gaGFzIHRvIHN1YnRyYWN0IHRvIGZ1bGZpbGwgcmVxdWlyZW1lbnRzIGdpdmVuIGluIHRoZSB0YXNrIHN0YXRlbWVudCBhYm92ZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #6 3번