어떤 문제인가?

연산자를 사용하는 모든 경우의 수를 통해 최대값 및 최소값을 구하는 문제.
15649번 문제의 응용.

내 풀이

#include <stdio.h>

int m=1000000000,M=-1000000000,N,A[100];
char v[12]={0},Op[99],O[4]={'+','-','*','/'};

void d(int l, int S) {
    int i,t;
    if(l==N-1) {
        m=m>S?S:m;
        M=M<S?S:M;
        return;
    }
    for(i=0;i<N-1;i++) {
        if(!v[i]) {
            v[i]=1;
            t=S;
            if(Op[i]=='+') S+=A[l+1];
            if(Op[i]=='-') S-=A[l+1];
            if(Op[i]=='*') S*=A[l+1];
            if(Op[i]=='/') S/=A[l+1];
            d(l+1, S);
            S=t;
            v[i]=0;
        }
    }
}

int main() {
    int i=0,j,k=0;
    scanf("%d",&N);
    for(;i<N;i++) scanf("%d",&A[i]);
    for(i=0;i<N-1;) {
        for(scanf("%d",&j);j>0;j--) Op[i++]=O[k];
        k++;
    }
    d(0, A[0]);
    printf("%d\n%d",M,m);
}

생각보다 어렵진 않았다. 기본 조건을 생각하고 반복 조건을 생각하니 크게 막히는 부분 없이 풀렸다.

남들의 풀이

물론 내 풀이에서 간략하게 만들 수 있는 부분은 많았다.

#include<stdio.h>
#include<limits.h>

int arr[11];
int max=INT_MIN;
int min=INT_MAX;

void find(int a,int b,int c,int d,int sum,int i)
{
	if(a==0&&b==0&&c==0&&d==0)
	{
		if(max<sum) max=sum;
		if(min>sum) min=sum;
		return;
	}
	if(a>0) 
	find(a-1,b,c,d,sum+arr[i],i+1);
	if(b>0)
	find(a,b-1,c,d,sum-arr[i],i+1);
	if(c>0)
	find(a,b,c-1,d,sum*arr[i],i+1);
	if(d>0)
	find(a,b,c,d-1,sum/arr[i],i+1);
}
	

int main(void)
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	scanf("%d",&arr[i]);
	int a,b,c,d;
	scanf("%d%d%d%d",&a,&b,&c,&d);
	find(a,b,c,d,arr[0],1);
	printf("%d\n%d",max,min);
	return 0;
}

sangchu8864님의 코드
-> https://www.acmicpc.net/source/29992992

1. 내 코드는 중간값 S에 직접 간섭하는 부분이 있다.
   -> 그렇기 때문에 연산이 끝나면 다시 되돌리는 부분을 삽입해야 했다.
   -> 그럴 필요 없이 바로 계산 결과만 넘겨주면 된다.
2. 문자열 따위 필요 없다. 결국 n번째 요소 아니던가? 이를 이용하면 더 줄일 수 있다.