View problem - 전화번호 나누기 (KPI13_telephone)

Language	Compilation command
C11	/usr/bin/gcc -DEVAL -std=gnu11 -O2 -pipe -static -s -o telephone telephone.c -lm
C++20	/usr/bin/g++ -DEVAL -std=gnu++20 -O2 -pipe -static -s -o telephone telephone.cpp
C++17	/usr/bin/g++ -DEVAL -std=gnu++17 -O2 -pipe -static -s -o telephone telephone.cpp
Java	/usr/bin/javac -encoding UTF-8 telephone.java /bin/sh -c echo "Main-Class: telephone" > __manifest__.txt /bin/sh -c jar cfm telephone.jar __manifest__.txt *.class
Pypy 3	/usr/bin/pypy3 -m compileall -b telephone.py /bin/mv telephone.pyc __main__.pyc /usr/bin/zip telephone.pyz.zip __main__.pyc /bin/mv telephone.pyz.zip telephone.pyz

Time limit	Memory limit	# of submissions	# of submitted users	Solved #	Accepted user ratio
1000 ms	64 MiB	13	1	1	100.00%

전화번호 사이에 하이픈(-)을 넣는 것은 일상적인 일입니다. 예로 들어서, 전화번호 1245633은 124-56-33 또는 12-45-633으로 쓰일 수 있습니다. 우리는 하이픈으로 구분된 각 부분을 숫자로 여기고 이 숫자들의 합을 구할 수 있습니다. 예로 들어, 124-56-33의 각 부분의 합은 $124+56+33=213$입니다. 승현이는 전화번호가 주어질 때, 이를 $k$개의 부분으로 적당히 나누어 합을 최소화하도록 하고자 합니다.

입력 형식

첫 번째 줄에 0부터 9까지의 숫자들로만 구성된 전화번호 $n$과 전화번호를 하이픈으로 나눌 부분의 수 $k$가 주어집니다. $n$의 길이는 최소 1, 최대 100입니다. $k$는 $n$의 길이보다 크지 않습니다.

출력 형식

$n$을 $k$개 부분으로 나눌 때 합의 최솟값을 출력합니다.

예제

예제 1

입력

1245633 3

출력

예제 2

입력

00000000000000000000012 4

출력

설명

첫 번째 예제에서 최적으로 나누면 124-56-33이 됩니다. 두 번째 예제에는 최적으로 나누는 경우가 많은데, 그 중 하나는 00000-000000000-00000001-2입니다.

Problem Source

KPI-OPEN 2013 2nd Round Problem H