85. 수식 만들기 [DFS]

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

 

풀이 

- DFS 문제

+ - * / 개수가 주어지는데 이를 사용해서 DFS함수를 작성하는게 제대로 떠오르지 않았다

 op[0]>0이면 더하기를 사용해야 한다는 것이고 op[0]--해서 DFS(L+1, res+a[L])로 뻗어 나간다.

배열엔 n-1번까지 수가 들어가기 때문에 종료조건은 L==n일 때이다. (n+1과 혼동 주의)

(중요!!) 종료 후엔 op[0]++해서 개수를 복구시켜야 한다.

 

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
int n, maxi=2147000000, mini=-2147000000;
int a[20],op[5];

//85. 수식 만들기
void DFS(int L, int res){
    if(L==n){
        //배열이 n-1까지니까 n이면 종료
        if(res>maxi) maxi=res;
        if(res<mini) mini=res;
    }else{
        if(op[0]>0){
            op[0]--;
            DFS(L+1, res+a[L]);
            op[0]++;
        }
        if(op[1]>0){
            op[1]--;
            DFS(L+1, res-a[L]);
            op[1]++;
        }
        if(op[2]>0){
            op[2]--;
            DFS(L+1, res*a[L]);
            op[2]++;
        }
        if(op[3]>0){
            op[3]--;
            DFS(L+1, res/a[L]);
            op[3]++;
        }
    }
}

int main(){
    int i;
    scanf("%d", &n);
    for(i=0;i<n;i++){
        scanf("%d", &a[i]);
    }
    for(i=0;i<4;i++){
        scanf("%d", &op[i]);
    }
    DFS(1, a[0]); //첫번째 숫자 넘어감
    printf("%d\n%d\n", maxi, mini);
    return 0;
}