[백준/c++] BOJ 14395 - 4연산

https://www.acmicpc.net/problem/14395

14395번: 4연산

 

문제 설명

정수 s가 주어진다. 정수 s를 t로 바꾸는 최소 연산 횟수를 구하는 프로그램을 작성한다.

사용할 수 있는 연산은 아래와 같다.

 

1. s = s + s; ( 출력 : + )

2. s = s - s; ( 출력 : - )

3. s = s * s; ( 출력 : * )

4. s = s / s; ( 출력 : / ) ( s가 0이 아닐 때만 사용 가능)

(1 <= s, t <= 10^9)

해결

bfs를 돌며 숫자들을 계산한다.

visited를 위해 set을 이용하였다.

 

queue에 string을 넣어 bfs를 돌며 계산한 연산자를 순서대로 저장한다.

숫자가 t와 같다면 string을 리턴한다.

코드

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

long long a, b;
set<long long> visited;
char cal[4] = { '*', '+', '-', '/' };

long long func(long long num, char ope) {
    if (ope == '+') return num + num;
    if (ope == '-') return num - num;
    if (ope == '*') return num * num;
    return num / num;
}

int range_over(long long num) {
    return num < 0 || num > 1000000001;
}

string bfs() {
    queue<pair<long long, string>> q;
    q.push({ a, "" });
    visited.insert(a); 

    while (!q.empty()) {
        auto cur = q.front(); q.pop();
        for (int dir = 0; dir < 4; dir++) {
            if (cur.x == 0 && dir == 3) continue;
            long long num = func(cur.x, cal[dir]);
            if (range_over(num) || visited.count(num)) continue;
            if (num == b)
                return cur.y + cal[dir];
            visited.insert(num);
            q.push({ num, cur.y + cal[dir] });
        }
    }
    return "-1";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> a >> b;
    if (a == b) {
        cout << 0;
        return 0;
    }
    cout << bfs() << "\n";
}