[BOJ]14888_연산자 끼워넣기_C언어

• 알고리즘 유형 : DFS
• 풀이 참고 : https://velog.io/@kimmainsain/C%EC%96%B8%EC%96%B4-%EB%B0%B1%EC%A4%80-14888-%EC%97%B0%EC%82%B0%EC%9E%90-%EB%81%BC%EC%9B%8C%EB%84%A3%EA%B8%B0
• 문제 링크 : https://www.acmicpc.net/problem/14888

---

풀이 요약

각 연산종류마다의 주어진 개수만큼 dfs함수를 실행하여 준다. 

이때 x라는 변수를 하나씩 더하여 다음과 같은 사항을 체크한다. 

1. dfs 깊이

2. arr 리스트의 인덱스 번호

따라서 주어진 연산 개수만큼 계산이 된다. 

 

그리고 max값을 문제에서 주어진 범위의 가장 작은 수로 제한을 두어 비교하며 업데이트 한다. 

(min값 동일)

---

코드(C)

#include <stdio.h>

int n;
int min = 100000001;
int max = -10000000;
int arr[12];

void DFS(int plus, int minus, int mult, int div, int x, int sum)
{
    if (x == n -1)
    {
        if (max < sum) (max = sum);
        if (min > sum) (min = sum);
    }
    if (plus > 0)
        DFS(plus - 1, minus, mult, div, x + 1, sum + arr[x + 1]);
    if (minus > 0)
        DFS(plus, minus - 1, mult, div, x + 1, sum - arr[x + 1]);
    if (mult > 0)
        DFS(plus, minus, mult - 1, div, x + 1, sum * arr[x + 1]);
    if (div > 0)
        DFS(plus, minus, mult, div - 1, x + 1, sum / arr[x + 1]);
}

int main()
{
    int plus, minus, mult, div, i;
    scanf("%d", &n);
    i = 0;
    while (i<n)
    {
        scanf("%d", &arr[i]);
        i++;
    }
    scanf("%d %d %d %d", &plus, &minus, &mult, &div);
    DFS(plus, minus, mult, div, 0, arr[0]);
    printf("%d\n%d", max, min);
    
}

---

배운 점, 배울 점

1. scanf() 함수 사용법

  - 조금 복잡하지만 단순히 정리하면 사용자(input값)에게 받은 값을 미리 선언한 변수(주소)로 데이터를 넣겠다. 이다. 

  - 그래서 문자열이 아니면 scanf에는 &가 들어가게 되는 것이다. 

2. 최대/소값 구하는 문제에서 미리 세팅하는 기본값은 많이 사용되는 방법이니 잘 알아두자.