[14888] 연산자 끼워넣기

[14888] 연산자 끼워넣기 (http://boj.kr/14888)

1) Brute Force 풀이

< 소스코드 >

#include <stdio.h>
 
int a[15], op[4];
 
int ansN = 1e9;
int ansX = -1e9;
int set[15];
 
void go(int n, int ps, int mi, int mu, int dv)
{
    if(n == 1) {
        int ans = a[1];
        for(int i=2; set[i]; i++) {
            if(set[i] == 1) ans += a[i];
            else if(set[i] == 2) ans -= a[i];
            else if(set[i] == 3) ans *= a[i];
            else {
                if(ans < 0) {
                    ans *= -1;
                    ans /= a[i];
                    ans *= -1;
                }
                else
                    ans /= a[i];
            }
        }
        if(ans > ansX) ansX = ans;
        if(ans < ansN) ansN = ans;
    }
 
    if(ps) { set[n]=1; go(n-1, ps-1, mi, mu, dv); }
    if(mi) { set[n]=2; go(n-1, ps, mi-1, mu, dv); }
    if(mu) { set[n]=3; go(n-1, ps, mi, mu-1, dv); }
    if(dv) { set[n]=4; go(n-1, ps, mi, mu, dv-1); }
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for(int i=1; i<=n; i++)
        scanf("%d", a+i);
 
    for(int i=0; i<4; i++)
        scanf("%d", op+i);
 
    go(n, op[0], op[1], op[2], op[3]);
    printf("%d\n%d\n", ansX, ansN);
    return 0;
}
 

>> 연산자 순서의 모든 경우의 수를 저장해 놓고, 그 순서에 맞게 계산을 한 다음 최대값과 최소값을 구한다.

2) DP 풀이

#include <stdio.h>
 
int a[15], op[4];
int d[15][15][15][15][15];
int e[15][15][15][15][15];
const int INF=1e9;
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int min(int a, int b)
{
    return a < b ? a : b;
}   
 
int maxV(int n, int ps, int mi, int mu, int dv)
{
    int ans = -INF;
    if(n == 1) return a[n];
    if(d[n][ps][mi][mu][dv]!=INF+1) return d[n][ps][mi][mu][dv];
 
    if(ps) ans = max(ans, maxV(n-1, ps-1, mi, mu, dv)+a[n]);
    if(mi) ans = max(ans, maxV(n-1, ps, mi-1, mu, dv)-a[n]);
    if(mu) ans = max(ans, maxV(n-1, ps, mi, mu-1, dv)*a[n]);
    if(dv) {
        int tmp = maxV(n-1, ps, mi, mu, dv-1);
        if(tmp < 0) { 
            tmp *= -1;
            tmp /= a[n];
            tmp *= -1;
        }
        else
            tmp /= a[n];
        ans = max(ans, tmp);
    }
    return d[n][ps][mi][mu][dv] = ans;
}
 
int minV(int n, int ps, int mi, int mu, int dv)
{
    int ans = INF;
    if(n == 1) return a[n];
    if(e[n][ps][mi][mu][dv]!=INF+1) return e[n][ps][mi][mu][dv];
 
    if(ps) ans = min(ans, minV(n-1, ps-1, mi, mu, dv)+a[n]);
    if(mi) ans = min(ans, minV(n-1, ps, mi-1, mu, dv)-a[n]);
    if(mu) ans = min(ans, minV(n-1, ps, mi, mu-1, dv)*a[n]);
    if(dv) {
        int tmp = minV(n-1, ps, mi, mu, dv-1);
        if(tmp < 0) { 
            tmp *= -1;
            tmp /= a[n];
            tmp *= -1;
        }
        else
            tmp /= a[n];
        ans = min(ans, tmp);
    }
    return e[n][ps][mi][mu][dv] = ans;
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for(int i=1; i<=n; i++)
        scanf("%d", a+i);
 
    for(int i=0; i<4; i++)
        scanf("%d", op+i);
 
    for(int i=0; i<15; i++)
        for(int j=0; j<15; j++)
            for(int k=0; k<15; k++)
                for(int l=0; l<15; l++)
                    for(int m=0; m<15; m++)
                        d[i][j][k][l][m] = e[i][j][k][l][m] = INF+1;
 
    printf("%d\n", maxV(n, op[0], op[1], op[2], op[3]));
    printf("%d\n", minV(n, op[0], op[1], op[2], op[3]));
    return 0;
}
 

>> 맨처음 풀이에 대해 잘못된 점을 파악한 다음(나눗셈에 대한 처리), 코드를 수정하니 AC 를 받았다.

>> 근데 다시생각해보면 왜 DP 로 가능한지 모르겠다...

< 마지막 테케가 안나오는 소스코드 >

#include <stdio.h>
 
int a[15], op[4];
int d[15][15][15][15][15];
int e[15][15][15][15][15];
const int INF=1e9;
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int min(int a, int b)
{
    return a < b ? a : b;
}   
 
int maxV(int n, int ps, int mi, int mu, int dv)
{
    int ans = -INF;
    if(n == 1) return a[n];
    if(d[n][ps][mi][mu][dv]!=INF+1) return d[n][ps][mi][mu][dv];
 
    if(ps) ans = max(ans, maxV(n-1, ps-1, mi, mu, dv)+a[n]);
    if(mi) ans = max(ans, maxV(n-1, ps, mi-1, mu, dv)-a[n]);
    if(mu) ans = max(ans, maxV(n-1, ps, mi, mu-1, dv)*a[n]);
    if(dv) {
        int tmp = maxV(n-1, ps, mi, mu, dv-1);
        if(tmp < 0) tmp *= -1;
        tmp /= a[n];
        tmp *= -1;
        ans = max(ans, tmp);
    }
    return d[n][ps][mi][mu][dv] = ans;
}
 
int minV(int n, int ps, int mi, int mu, int dv)
{
    int ans = INF;
    if(n == 1) return a[n];
    if(e[n][ps][mi][mu][dv]!=INF+1) return e[n][ps][mi][mu][dv];
 
    if(ps) ans = min(ans, minV(n-1, ps-1, mi, mu, dv)+a[n]);
    if(mi) ans = min(ans, minV(n-1, ps, mi-1, mu, dv)-a[n]);
    if(mu) ans = min(ans, minV(n-1, ps, mi, mu-1, dv)*a[n]);
    if(dv) {
        int tmp = minV(n-1, ps, mi, mu, dv-1);
        if(tmp < 0) tmp *= -1;
        tmp /= a[n];
        tmp *= -1;
        ans = min(ans, tmp);
    }
    return e[n][ps][mi][mu][dv] = ans;
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for(int i=1; i<=n; i++)
        scanf("%d", a+i);
 
    for(int i=0; i<4; i++)
        scanf("%d", op+i);
 
    for(int i=0; i<15; i++)
        for(int j=0; j<15; j++)
            for(int k=0; k<15; k++)
                for(int l=0; l<15; l++)
                    for(int m=0; m<15; m++)
                        d[i][j][k][l][m] = e[i][j][k][l][m] = INF+1;
 
    printf("%d\n", maxV(n, op[0], op[1], op[2], op[3]));
    printf("%d\n", minV(n, op[0], op[1], op[2], op[3]));
    return 0;
}

>> 마지막 테케의 최소값이 -36이 나온다..... -24 라는데...ㅜ

>> 가만 생각해보니 DP 가 아닌 것 같다. 모든 경우의 수를 생각해서 풀면 될 것 같은 생각이 든다. (brute force)

>> 나눗셈에 대한 처리를 잘못했다.