[Inflearn] 수식만들기(삼성 SW역량평가 기출 : DFS)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

    - 연산자는 덧셈, 뺄셈, 곱셈, 나눗셈

    - 수열의 순서는 유지한 채 각 항사이에 N-1개의 연산자를 적절히 배치

    - 연산자 우선순위를 따지지 않고 맨 앞쪽 연산자부터 차례로 계산

    - 연산 결과가 최대인 것과 최소인 것을 출력

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

입력이 아래와 같을 때,

3

5 3 8 

1 0 1 0

수열 : 5 3 8

연산자 : +, *

5 + 3 * 8 = 64

5 * 3 + 8 = 23

DFS 함수를 만들 때 먼저 

종료 조건을 생각해보라고 했다.

종료 조건은 연산자의 사용 횟수가 처음에 1로 시작하였으므로,

n고 같아지면 종료되야한다.

n과 같아졌을 때, 최대, 최솟값을 구해주면 되겠다.

그럼 연산자의 사용 횟수가 n과 다를 경우,

사용할 연산자가 있다면 그 연산자를 사용해서 연산 결과를 재귀함수로 넘겨주고,

재귀함수가 끝나면 다시 연사자를 돌려놓는다.

과정은 알겠다만.. 

아직까지도 DFS는 헷갈리다ㅠㅠ

문제가 이렇게 복잡해지면 너무 복잡하게만 느껴진다..

알고보면 하나도 복잡한게 아닌데.. 

DFS 문제를 많이 풀어봐야겠다..!!

#. Code

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
 
int a[20], op[5], n, maxi = -2147000000, mini = 2147000000;
 
void DFS(int L, int res) {
    if (L == 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() {
    freopen("input.txt", "rt", stdin);
    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;
}

line 43~48) 사용할 배열은 자연수를 저장하는 배열과 연산자의 개수를 저장하는 배열이다.

line 50) 초기 DFS() 호출 시, 초기값 a[0]을 넘겨주어야하므로 level은 1로 넘겨준다.

          (이미 a[0]을 사용하였으므로, level은 사용할 자연수의 위치이자 사용한 자연수의 개수라고 생각하면 되겠다.)

line 8~35) DFS()함수는 level과 연산결과를 인자로 받는다.

line 9~12) level == n 이 되면 종료조건을 만족하게되어 연산의 최대, 최솟값을 저장한다.

line 13~34) 종료조건을 만족하지 않는다면 각 연산자별로 동작을 수행하는데,

    사용할 연산자가 있다면 해당 연산자를 사용하고 op[n]--

    leveld 을 1 올려주고, 해당 연산자로 연산을 수행한 결과를 DFS()에 넘겨준다.

    DFS() 동작을 완료하면 사용한 연산자를 돌려준다 op[n]++

이 DFS 문제를 풀면서 나의 문제는

어떤 값을 level 로 사용할지 제대로 선택하지 못 했다.

나는 level 을 넘겨주는 용도로만 사용하였고, 자연수랑 연산자를 한 반복문에서 같이 해결하려고 하다보니

계속 엉키고 엉켰다..

재귀함수 종료조건은 그래도 이제 나름 잘 정하고있지만,,

더 중요한 동작 구현이 잘 되고있지 않다.. DFS() 구현 시 어떤 값을 level로 사용할지 더 생각해보자!

#. Result

  - Input --------------------------------------------------------

3

5 3 8

1 0 1 0

------------------------------------------------------------------

  - Output --------------------------------------------------------

64

23

------------------------------------------------------------------