5. 숫자를 4단으로 나누면 4단의 곱셈을 최소화할 수 있다[dp]

제목은 숫자(10000~100000000)를 주고 이 숫자를 4단으로 나누어 4단의 곱셈을 최소화하는 방법이다.예를 들어 12345는 1*2*3*45=270, 10000=1*00*0*0=0으로 나뉜다.
문제 풀이 분석은 잠시 후에...
My Code:
 

#include <iostream>
#include <string>
using namespace std;

int dp[5][20];

int num(const string &str,int b,int e)
{
    b--;
    e--;
	int res=0;
	while(b<=e)
	{
		res=(str[b++]-'0')+res*10;
	}
	return res;
}

int main()
{
	for(int i=0;i<5;i++)
		for(int j=0;j<20;j++)
			dp[i][j]=1;

	string str;
	cin>>str;
	int len=str.size();

	for(int i=1;i<=4;i++)
        for(int j=i;j<=len;j++)
        {
            if(i==j)
            {
                int res=1;
                for(int t=0;t<j;t++)
                {
                    res*=(str[t]-'0');
                }
                dp[i][j]=res;
            }
            else if(i!=1)
            {
                int min=0x7FFFFFFF;
                for(int k=i-1;k<j;k++)
                {
                    int temp=dp[i-1][k]*num(str,k+1,j);
                    if(temp<min)
                    min=temp;
                }
                dp[i][j]=min;
            }
            else if(i==1)
            {
                dp[i][j]=num(str,1,j);
            }

        }
    cout<<dp[4][len]<<endl;
	return 0;
}