문제

문제 링크

어떻게 접근할 것인가

  • 연산자 하나를 쓴 상태로 다음 상태로 계속 진행한다.
  • 연산자를 다 사용하면 백트랙해서 다른 연산자를 넣어준다.
  • 연산 결과 최고와 최저를 저장한다.

코드

#include <cstdio>
int n, o[4], arr[10], M = -1000000000, m = 1000000000;

void find(int cnt, int r){
    if(cnt == n){
        if(r > M) M = r;
        if(r < m) m = r;
        return;
    }
    for(int i = 0; i < 4; i++){
        if(o[i]){
            o[i]--;
            if(i == 0)find(cnt+1, r+arr[cnt]);
            else if(i == 1)find(cnt+1, r-arr[cnt]);
            else if(i == 2)find(cnt+1, r*arr[cnt]);
            else find(cnt+1, r/arr[cnt]);
            o[i]++;
        }
    }
}
int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++)scanf("%d", &arr[i]);
    for(int i = 0; i < 4; i++)scanf("%d", &o[i]);
    find(1, arr[0]);
    printf("%d\n%d", M, m);
}

느낀점

  • 브루트포스를 백트래킹으로 가볍게 패쓰~!!