연산자 끼워넣기 (DFS풀이)


작성일 : 2018-12-03 00:44:51
조회수 : 184


본문

DFS로 풀 수 있는 방법은 여러가지가 있겠지만, 저같은 경우는 각 연산자의 개수를 배열에 저장하고, 각 dfs 단계에서 1개 이상 존재하는 연산자에 대해 1개를 빼고 다음 단계로 진입한 뒤, 현재 단계에 돌아오면 다시 1개를 돌려주는 방식으로 설계를 하였습니다. 결과적으로 완전 탐색이 가능해집니다.


#include <iostream>

using namespace std;


int n, k, no[11], ari[4], ap = 0, ans1 = -2e9, ans2 = 2e9;

void dfs(int now, int idx) {

    if (idx == n-1) {

        ans1 = ans1 < now ? now : ans1;

        ans2 = ans2 > now ? now : ans2;

        return;

    }

    for (int i = 0; i < 4; i++) {

        if (ari[i]) {

            ari[i]--;

            if (i == 0) dfs(now + no[idx + 1], idx + 1);

            if (i == 1) dfs(now - no[idx + 1], idx + 1);

            if (i == 2) dfs(now * no[idx + 1], idx + 1);

            if (i == 3) dfs(now / no[idx + 1], idx + 1);

            ari[i]++;

        }

    }

}

int main() {

    cin >> n;

    for (int i = 0; i < n; i++) cin >> no[i];

    for (int i = 0; i < 4; i++) cin >> ari[i];

    dfs(no[0], 0);

    cout << ans1 << "\n" << ans2;

}

연산자 끼워넣기 (DFS풀이) - 알고리즘닷컴
취업 대비 알고리즘에서는 다양한 기업들의 기출 문제 및 경향, 풀이 등에 대한 포스팅을 다룹니다.