[백준 / BOJ] 14888번 연산자 끼워넣기 (C++, Python)

링크 : https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

---

문제

---

문제 풀이

우선 나는 문제 접근을 하나씩 다 해보는건 어떨까? 하는 생각에서 시작했다. 연산자의 우선순위는 생각하지 않는다고 했으니 첫번째부터 차근차근 사칙연산을 하면 성공할 것 같다고 생각했다.

 

C++ 상세 풀이

원래 전역변수를 남발하는 것은 좋지 않다고 배워서 쓰지 않으려고 노력했는데, 항상 백트래킹 문제를 풀다 보면 매개변수로 넣었을 때 코드가 좀 더러운 것 같기도 하고 이번 문제는 넣어야하는 것도 많아 전부 전역변수로 밀어넣었다.

 

void dfs(int cur, int res) {
    if (cur == N) {
        res_min = std::min(res_min, res);
        res_max = std::max(res_max, res);
        return;
    }

    for (int i = 0; i < 4; ++i) {
        if (operators[i] == 0)
            continue;

        operators[i]--;

        if (i == 0)
            dfs(cur + 1, res + arr[cur]);
        else if (i == 1)
            dfs(cur + 1, res - arr[cur]);
        else if (i == 2)
            dfs(cur + 1, res * arr[cur]);
        else if (i == 3)
            dfs(cur + 1, res / arr[cur]);
        
        operators[i]++;
    }
}

우선 매개변수로 cur, res를 넣어주었다. cur은 현재 몇 번째 숫자까지 넣었는지, res는 합계다.

cur이 N과 같다면 모든 숫자를 다 연산했다는 의미이므로 res가 각각 res_min보다 작은지, res_max보다 큰지 판별해서 넣도록 했다. 전에 저장했었던 res_min, res_max를 활용해서 최대/최소를 구하는 과정이다.

그리고 연산자는 총 4개이니 for문을 4번 돌도록 하고, operators[i]가 0이라면 해당 연산자가 아무것도 없다는 것을 뜻하니 continue로 다음 연산자를 사용하도록 했다. 나머지는 다시 재귀하도록 하면 된다. 또한 증감연산자를 활용해 연산자의 사용 여부를 적용시켜주었다.

Python 상세 풀이

항상 내가 C++을 먼저 풀고 파이썬을 풀어서 그런지 몰라도 C++식으로 풀게 되는 것 같아 다음부터는 파이썬을 먼저 풀어야 할 것 같다. 더 무궁무진한 방법이 가능한데 너무 틀에 박혀서 그대로 갖다 옮겨놓는 것 같다.

파이썬은 정말 더 잘 구현하신 분들이 많아 링크를 하나 첨부해본다. (여기를 클릭) 

 

def dfs(cur, res):
    global res_min, res_max
    
    if cur == N:
        res_min = min(res_min, res)
        res_max = max(res_max, res)
        return
    
    for i in range(4):
        if operators[i] == 0:
            continue

        operators[i] -= 1

        if i == 0:
            dfs(cur + 1, res + arr[cur])
        elif i == 1:
            dfs(cur + 1, res - arr[cur])
        elif i == 2:
            dfs(cur + 1, res * arr[cur])
        elif i == 3:
            dfs(cur + 1, int(res / arr[cur]))
        
        operators[i] += 1

우선 매개변수로 cur, res를 넣어주었다. cur은 현재 몇 번째 숫자까지 넣었는지, res는 합계다.

cur이 N과 같다면 모든 숫자를 다 연산했다는 의미이므로 res가 각각 res_min보다 작은지, res_max보다 큰지 판별해서 넣도록 했다. 전에 저장했었던 res_min, res_max를 활용해서 최대/최소를 구하는 과정이다.

그리고 연산자는 총 4개이니 for문을 4번 돌도록 하고, operators[i]가 0이라면 해당 연산자가 아무것도 없다는 것을 뜻하니 continue로 다음 연산자를 사용하도록 했다. 나머지는 다시 재귀하도록 하면 된다. 또한 증감연산자를 활용해 연산자의 사용 여부를 적용시켜주었다.

 

C++ 코드 전문

Python 코드 전문

 

소감

너무 어렵게 생각했다가 시간을 많이 뺏긴 문제다. 일단 브루트 포스로 먼저 생각해보자.