BOJ 1955 수식 표현

BOJ 1955 수식 표현

[분류 : 다이나믹 프로그래밍]

[풀이]

  할 수 있는 연산을 생각해보자.

1. 덧셈
2. 곱셈
3. 팩토리얼

  여기 세 가지 연산에서 항으로 들어갈 수 있는 표현식도 생각해보자. 대신 마지막 표현식만 생각하자. 표현식을 e1, e2로 둘 때 e1+e2, e1*e2, e1!로 표현이 가능하다. 

  따라서 n이 주어지면 1.에서는 단순 덧셈으로 구간을 나누고, 2.에서는 약수 판별을, 3.에서는 현재 값이 특정 표현식 e1의 팩토리얼인지 확인해서 다이나믹을 구성해주면 된다. 특정 표현식이라고 표기한 이유는 6! = (3!)!일 수도, (1+5)!일 수도 있기 때문이다.

 

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAX_N = 1e4 + 1;
int main() {
    int n, i, j, dp[MAX_N] = { 0, 1 }, fac[9] = { 1 }, sqrtn;
    for (i = 1; i < 9; i++) fac[i] = fac[i - 1] * i;
    scanf("%d", &n);
    for (i = 2; i <= n; i++) {
        int& ret = dp[i];
        ret = i;
        for (j = 1; j <= i / 2; j++)
            ret = min(ret, dp[j] + dp[i - j]); // +
        sqrtn = sqrt(i);
        for (j = 2; j <= sqrtn; j++) if (i % j == 0)
            ret = min(ret, dp[j] + dp[i / j]); // *
        for (j = 2; j < 9; j++) if (i == fac[j]) // !
            ret = min(ret, dp[j]);
    }
    printf("%d", dp[n]);
    return 0;
}