백준 1955: 수식 표현

https://www.acmicpc.net/problem/1955

1955번: 수식 표현

시간복잡도: n이 10000 이하이기 때문에 O(n^2) 안에 풀 수 있어야 한다.

PART 0.

입력이 i일때 출력해야할 값을 dp[i]라고 두면
일단 dp[0]~dp[8] 값을 생각해보자면
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
dp[4] = 4;
dp[5] = 5;
dp[6] = 3;
dp[7] = 4;
dp[8] = 5;

PART 1.

dp[i]에서 i가 어떤 자연수 k에 대해 k!일 때(i는 10000 이하이기 떄문에 k는 최대 7)
dp[i]=dp[k];
라고 두면 된다.
왜냐하면 k를 만드는 수식에 느낌표만 붙이면 1을 더 사용하지 않고 i를 표현하는 수식이 완성되기 때문이다.

PART 2.

이제 i가 어떤 자연수의 팩토리얼이 아닐 때,
i는
1. e1+e2 형태로 덧셈으로 이어진 식이거나,
2. e1*e2 형태로 곱셈으로 이어진 식
무조건 둘 중 하나이다.

식 e1가 표현하는 수가 j이면
1. e2는 i-j를 표현하는 식이거나,
2. e2는 i/j를 표현하는 식이거나 (단, i는 j로 나뉘어 떨어지는 경우만)

따라서 j<i인 모든 자연수 j에 대해
dp[j]+d[i-j], dp[i/j]+dp[j] (i가 j로 나뉘어 떨어지는 경우)
들을 전부 계산한 뒤 이 중 가장 작은 값을 dp[i]로 설정하면 된다.

다음은 C언어로 구현한 코드이다.

int min(int n, int m)
{
    return (n < m) ? n : m;
}
 
 
int main()
{
    int n;
    scanf("%d", &n);
    //PART 0
    int dp[10005] = { 0 };
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 3;
    dp[4] = 4;
    dp[5] = 5;
    dp[6] = 3;
    dp[7] = 4;
    dp[8] = 5;
 
    //PART 1
    int k = 2;
    for (int i = 3;i <= 7;i++)
    {
        k *= i;
        dp[k] = dp[i];
    }
 
    //PART 2
    for (int i = 9;i < 10001;i++)
    {
        if (dp[i])
            continue;
        dp[i] = 2100000000;
        for (int j = 1;j < i;j++)
        {
            dp[i] = min(dp[i], dp[i / j] + dp[j] + dp[i % j]);
 
            dp[i] = min(dp[i], dp[i - j] + dp[j]);
        }
    }
    printf("%d", dp[n]);
    
}

 

 

시간복잡도는 O(n^2)이다.