시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 130 64 42 47.727%

문제

길이가 N인 막대 모양 과자가 있다. 성관이와 도토리는 이 과자를 여러 조각으로 잘라 각자 합이 N/2가 되도록 나눠먹으려 한다. 이 과자는 무엇인지 모를 재료로 만들어졌기 때문에 각 지점마다 자를 때 필요한 힘이 다르다. 알고리즘 캠프를 하느라 너무 지친 성관이는 과자를 자르기 위해 많은 힘을 쓰고 싶지 않다. 과자의 각 위치를 절단하는데 얼마의 힘이 필요한지를 알 때, 두 사람이 과자를 나누기 위해 필요한 최소 힘의 합을 구해주자.

 예를 들어 길이 6인 과자가 있고, 각 지점을 자르는 데 필요한 힘이 왼쪽부터 {1, 8, 12, 6, 2}라면 이 때 필요한 최소 힘은 다음과 같이 잘랐을 때의 합인 7이 된다.

입력

첫 줄에 과자의 길이 N(2 ≤ N ≤ 10,000)이 주어진다. 이 때 N은 짝수이다. 두 번째줄부터 N번째 줄까지 맨 왼쪽에서부터 각 지점을 자르는 데 필요한 힘 P(0 ≤ P ≤ 10,000)가 주어진다.

출력

한 줄에 필요한 최소 힘의 합을 출력하라.

예제 입력 1

6
1
8
12
6
2

예제 출력 1

7

힌트

W3sicHJvYmxlbV9pZCI6IjU1NjEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZmNcdWM3OTBcdWM3NTggXHViZDg0XHVkNTYwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWFlMzhcdWM3NzRcdWFjMDAgTlx1Yzc3OCBcdWI5YzlcdWIzMDAgXHViYWE4XHVjNTkxIFx1YWNmY1x1Yzc5MFx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YzEzMVx1YWQwMFx1Yzc3NFx1YzY0MCBcdWIzYzRcdWQxYTBcdWI5YWNcdWIyOTQgXHVjNzc0IFx1YWNmY1x1Yzc5MFx1Yjk3YyBcdWM1ZWNcdWI3ZWMgXHVjODcwXHVhYzAxXHVjNzNjXHViODVjIFx1Yzc5OFx1Yjc3YyBcdWFjMDFcdWM3OTAgXHVkNTY5XHVjNzc0IE5cLzJcdWFjMDAgXHViNDE4XHViM2M0XHViODVkIFx1YjA5OFx1YjIyMFx1YmEzOVx1YzczY1x1YjgyNCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWFjZmNcdWM3OTBcdWIyOTQgXHViYjM0XHVjNWM3XHVjNzc4XHVjOWMwIFx1YmFhOFx1Yjk3YyBcdWM3YWNcdWI4Y2NcdWI4NWMgXHViOWNjXHViNGU0XHVjNWI0XHVjODRjXHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWFjMDEgXHVjOWMwXHVjODEwXHViOWM4XHViMmU0IFx1Yzc5MFx1Yjk3YyBcdWI1NGMgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1ZDc5OFx1Yzc3NCBcdWIyZTRcdWI5NzRcdWIyZTQuIFx1YzU0Y1x1YWNlMFx1YjlhY1x1Yzk5OCBcdWNlYTBcdWQ1MDRcdWI5N2MgXHVkNTU4XHViMjkwXHViNzdjIFx1YjEwOFx1YmIzNCBcdWM5YzBcdWNlNWMgXHVjMTMxXHVhZDAwXHVjNzc0XHViMjk0IFx1YWNmY1x1Yzc5MFx1Yjk3YyBcdWM3OTBcdWI5NzRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YjljZVx1Yzc0MCBcdWQ3OThcdWM3NDQgXHVjNGYwXHVhY2UwIFx1YzJmNlx1YzljMCBcdWM1NGFcdWIyZTQuIFx1YWNmY1x1Yzc5MFx1Yzc1OCBcdWFjMDEgXHVjNzA0XHVjZTU4XHViOTdjIFx1YzgwOFx1YjJlOFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWM1YmNcdWI5YzhcdWM3NTggXHVkNzk4XHVjNzc0IFx1ZDU0NFx1YzY5NFx1ZDU1Y1x1YzljMFx1Yjk3YyBcdWM1NGMgXHViNTRjLCBcdWI0NTAgXHVjMGFjXHViNzhjXHVjNzc0IFx1YWNmY1x1Yzc5MFx1Yjk3YyBcdWIwOThcdWIyMDRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWNkNWNcdWMxOGMgXHVkNzk4XHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWFkNmNcdWQ1NzRcdWM4ZmNcdWM3OTAuPFwvcD5cclxuXHJcbjxwPiZuYnNwO1x1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgXHVhZTM4XHVjNzc0IDZcdWM3NzggXHVhY2ZjXHVjNzkwXHVhYzAwIFx1Yzc4OFx1YWNlMCwgXHVhYzAxIFx1YzljMFx1YzgxMFx1Yzc0NCBcdWM3OTBcdWI5NzRcdWIyOTQgXHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWQ3OThcdWM3NzQgXHVjNjdjXHVjYWJkXHViZDgwXHVkMTMwIHsxLCA4LCAxMiwgNiwgMn1cdWI3N2NcdWJhNzQgXHVjNzc0IFx1YjU0YyBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1ZDc5OFx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1Yzc5OFx1Yjc5MFx1Yzc0NCBcdWI1NGNcdWM3NTggXHVkNTY5XHVjNzc4IDdcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC81NTYxXC8xLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIwM3B4OyB3aWR0aDozMzZweFwiIFwvPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWFjZmNcdWM3OTBcdWM3NTggXHVhZTM4XHVjNzc0IE4oMiAmbGU7IE4gJmxlOyAxMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YjU0YyBOXHVjNzQwIFx1YzlkZFx1YzIxOFx1Yzc3NFx1YjJlNC4gXHViNDUwIFx1YmM4OFx1YzlmOFx1YzkwNFx1YmQ4MFx1ZDEzMCBOXHViYzg4XHVjOWY4IFx1YzkwNFx1YWU0Y1x1YzljMCBcdWI5ZTggXHVjNjdjXHVjYWJkXHVjNWQwXHVjMTFjXHViZDgwXHVkMTMwIFx1YWMwMSBcdWM5YzBcdWM4MTBcdWM3NDQgXHVjNzkwXHViOTc0XHViMjk0IFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVkNzk4IFAoMCAmbGU7IFAgJmxlOyAxMCwwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWNkNWNcdWMxOGMgXHVkNzk4XHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTU2MSIsInByb2JsZW1fbGFuZyI6IjIiLCJ0aXRsZSI6Ilx1MzA0YVx1ODNkM1x1NWI1MFx1MzA2ZVx1NTIwNlx1NTI3MiIsImRlc2NyaXB0aW9uIjoiPHA+XHU5NTc3XHUzMDU1IE4gXHUzMGRmXHUzMGVhXHUzMGUxXHUzMGZjXHUzMGM4XHUzMGViXHUzMDZlXHU2OGQyXHU3MmI2XHUzMDZlXHUzMDRhXHU4M2QzXHU1YjUwXHUzMDRjIDEgXHU2NzJjXHUzMDQyXHUzMDhiXHVmZjA4XHUzMDUzXHUzMDUzXHUzMDY3IE4gXHUzMDZmXHU1MDc2XHU2NTcwXHVmZjA5XHVmZjBlMiBcdTRlYmFcdTMwNmUgSk9JXHU5NWEyXHU0ZmMyXHU4MDA1XHUzMDRjXHVmZjBjXHUzMDUzXHUzMDZlXHUzMDRhXHU4M2QzXHU1YjUwXHUzMDkyXHU4OTA3XHU2NTcwXHU2NzJjXHUzMDZiXHU1MjA3XHU2NWFkXHUzMDU3XHUzMDY2XHVmZjBjXHU1NDA4XHU4YTA4IE5cLzJcdTMwZGZcdTMwZWFcdTMwZTFcdTMwZmNcdTMwYzhcdTMwZWJcdTMwNWFcdTMwNjRcdTMwNmJcdTUyMDZcdTMwNTFcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNmJcdTMwNTdcdTMwNWZcdWZmMGU8XC9wPlxyXG5cclxuPHA+XHU3NDA2XHU3NTMxXHUzMDZmXHU0ZTBkXHU2NjBlXHUzMDY3XHUzMDQyXHUzMDhiXHUzMDRjXHVmZjBjXHUzMDUzXHUzMDZlXHUzMDRhXHU4M2QzXHU1YjUwXHUzMDZmXHU1ODM0XHU2MjQwXHUzMDZiXHUzMDg4XHUzMDYzXHUzMDY2XHU1MjA3XHU2NWFkXHUzMDZlXHUzMDU3XHUzMDg0XHUzMDU5XHUzMDU1XHUzMDRjXHU3NTcwXHUzMDZhXHUzMDYzXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlMiBcdTRlYmFcdTMwNmZcdWZmMGNcdTMwNGFcdTgzZDNcdTViNTBcdTMwOTJcdTVkZTZcdTMwNGJcdTMwODkgMSBcdTMwZGZcdTMwZWFcdTMwZTFcdTMwZmNcdTMwYzhcdTMwZWJcdTMwNTRcdTMwNjhcdTMwNmJcdThhYmZcdTMwNzlcdWZmMGNcdTU0MDRcdTU4MzRcdTYyNDBcdTMwNjdcdTUyMDdcdTY1YWRcdTMwNmJcdTRmNTVcdTc5ZDJcdTMwNGJcdTMwNGJcdTMwOGJcdTMwNGJcdTMwOTJcdTUyNzJcdTMwOGFcdTUxZmFcdTMwNTdcdTMwNWZcdWZmMGUyIFx1NGViYVx1MzA0Y1x1MzA0YVx1ODNkM1x1NWI1MFx1MzA5Mlx1NTIwNlx1MzA1MVx1MzA4Ylx1MzA1Zlx1MzA4MVx1MzA2ZVx1NTIwN1x1NjVhZFx1MzA2Ylx1MzA0Ylx1MzA0Ylx1MzA4Ylx1NzlkMlx1NjU3MFx1MzA2ZVx1NjcwMFx1NWMwZlx1NTAyNFx1MzA5Mlx1NmM0Mlx1MzA4MVx1MzA4Ylx1MzBkN1x1MzBlZFx1MzBiMFx1MzBlOVx1MzBlMFx1MzA5Mlx1NGY1Y1x1NjIxMFx1MzA1Ylx1MzA4OFx1ZmYwZTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHU1MTY1XHU1MjliXHUzMDZlIDEgXHU4ODRjXHU3NmVlXHUzMDZiXHUzMDZmXHVmZjBjXHU2OGQyXHUzMDZlXHU5NTc3XHUzMDU1IE4oMiAmbGU7IE4gJmxlOyAxMDAwMCBcdWZmMGNcdTMwNWZcdTMwNjBcdTMwNTcgTiBcdTMwNmZcdTUwNzZcdTY1NzApIFx1MzA0Y1x1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZVx1NTE2NVx1NTI5Ylx1MzA2ZSBpICsgMSBcdTg4NGNcdTc2ZWUgKDEgJmxlOyBpICZsZTsgTiAmbWludXM7IDEpIFx1MzA2Ylx1MzA2Zlx1ZmYwY1x1NWRlNlx1N2FlZlx1MzA0Ylx1MzA4OSBpIFx1MzBkZlx1MzBlYVx1MzBlMVx1MzBmY1x1MzBjOFx1MzBlYlx1NzZlZVx1MzA2ZVx1NTgzNFx1NjI0MFx1MzA2ZVx1NTIwN1x1NjVhZFx1MzA2Ylx1MzA0Ylx1MzA0Ylx1MzA4Ylx1NzlkMlx1NjU3MFx1MzA5Mlx1ODg2OFx1MzA1OVx1NjU3NFx1NjU3MCB0PHN1Yj5pPFwvc3ViPiAoMSAmbGU7IHQ8c3ViPmk8XC9zdWI+ICZsZTsgMTAwMDApIFx1MzA0Y1x1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZVx1NTIwN1x1NjVhZFx1NTNlZlx1ODBmZFx1MzA2YVx1NTgzNFx1NjI0MFx1MzA0Y04gJm1pbnVzOyAxIFx1N2I4N1x1NjI0MFx1MzA2N1x1MzA0Mlx1MzA4Ylx1MzA1M1x1MzA2OFx1MzA2Ylx1NmNlOFx1NjEwZlx1MzA1Ylx1MzA4OFx1ZmYwZTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPjIgXHU0ZWJhXHUzMDRjXHUzMDRhXHU4M2QzXHU1YjUwXHUzMDkyXHU1MjA2XHUzMDhiXHUzMDVmXHUzMDgxXHUzMDZlXHU1MjA3XHU2NWFkXHUzMDZiXHUzMDRiXHUzMDRiXHUzMDhiXHU3OWQyXHU2NTcwXHUzMDZlXHU2NzAwXHU1YzBmXHU1MDI0XHUzMDkyXHU1NDJiXHUzMDgwIDEgXHU4ODRjXHUzMDRiXHUzMDg5XHUzMDZhXHUzMDhiXHVmZjBlPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNzdjXHViY2Y4XHVjNWI0In1d

출처

Olympiad > 일본정보올림피아드 > JOI 2010 2번

  • 문제를 번역한 사람: Acka
  • 문제의 오타를 찾은 사람: anjupiter