[백준] 14395번 4연산 (C++)

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

 

 

이 문제는 정수 s와 t가 주어졌을때 4가지 연산을 최소로 사용하여 정수 s를 t로 바꾸는 연산의 개수를 출력하는 문제이다.

 

그렇다면 s에서 t의 최소 연산을 구하는 방법을 알아야하는데 

 

처음엔 그리디하게 접근을 해서 계속 s와 t의 차이가 클 경우 곱셈을 우선적으로 사용해야하나 생각을 해보았다.

 

결국 연산을 한 s를 같은 숫자를 더하고 곱하거나 빼거나 해야하기 때문에 값이 정확하게 t로 바꾸는 것은 그리디하게 풀 수 없다고 생각하였다.

 

그렇다면 할 수 있는 방법이 모든 경우의 방법을 구하는 것이다 즉 정수 s에서 4가지 연산을 사용한 값들에 대해서 

다시 4가지 연산을 사용하여 t로 만들 수 있는지 확인한다.

 

이때 다시 같은 값을 다시 연산을 하게 되는 경우가 생기는데 이것을 방문처리를 하기 위해서 집합(set)의 자료구조를 사용하여 최적화 하였다.

 

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

struct nutrition {
    int p;
    int f;
    int s;
    int v;
    int cost;
};

int dx[] = {0 ,0, -1, 0, 1, 1, -1, -1, 1};
int dy[] = {0, -1, 0, 1, 0, -1, 1, -1, 1};
ll s, t;
set<ll> st;

bool check(int a) {
    if(a < 0 || a > MAX) return false;

    if(st.find(a) != st.end()) {
        return false;
    }
    return true;
}

void bfs() {
    queue<tuple<ll, string>> q;
    q.push({s, ""});
    st.insert(s);

    while(!q.empty()) {
        ll x = get<0>(q.front());
        string sol = get<1>(q.front());
        q.pop();

        if(x == t) {
            cout << sol;
            exit(0);
        }

        for(int i = 0; i < 4; i++) {
            if(i == 0) {
                ll stand = x * x;
                if(check(stand)) {
                    q.push({stand, sol + '*'});
                    st.insert(stand);
                }
            }
            else if(i == 1) {
                ll stand = x + x;
                if(check(stand)) {
                    q.push({stand, sol + '+'});
                    st.insert(stand);
                }
            }
            else if(i == 2) {
                ll stand = x - x;
                if(check(stand)) {
                    q.push({stand, sol + '-'});
                    st.insert(stand);
                }
            }
            else {
                ll stand = x / x;
                if(check(stand)) {
                    q.push({stand, sol + '/'});
                    st.insert(stand);
                }
            }
        }
    }
}

void solve() {
    if(s == t) {
        cout << 0;
        return;
    }

    bfs();

    cout << -1;
}

void input() {
    cin >> s >> t;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}

 

먼저 bfs 함수 내부를 살펴보자

void bfs() {
    queue<tuple<ll, string>> q;
    q.push({s, ""});
    st.insert(s);

    while(!q.empty()) {
        ll x = get<0>(q.front());
        string sol = get<1>(q.front());
        q.pop();

        if(x == t) {
            cout << sol;
            exit(0);
        }

        for(int i = 0; i < 4; i++) {
            if(i == 0) {
                ll stand = x * x;
                if(check(stand)) {
                    q.push({stand, sol + '*'});
                    st.insert(stand);
                }
            }
            else if(i == 1) {
                ll stand = x + x;
                if(check(stand)) {
                    q.push({stand, sol + '+'});
                    st.insert(stand);
                }
            }
            else if(i == 2) {
                ll stand = x - x;
                if(check(stand)) {
                    q.push({stand, sol + '-'});
                    st.insert(stand);
                }
            }
            else {
                ll stand = x / x;
                if(check(stand)) {
                    q.push({stand, sol + '/'});
                    st.insert(stand);
                }
            }
        }
    }
}

 

처음 s노드를 삽입하여 4가지 연산을 사용하여 check함수에 인자로 넘겨준다. check 함수는 

set에 연산을 한 값이 있는지 없는지 확인하는 로직이다. 만약 없으면 아직 연산을 하지 않은것이기 때문에

큐에 다시 넣어주며 set에 넣어준다.

 

이후 x의 값이 t와 같은 경우 연산의 순서를 출력해주며 못만들경우 -1을 출력한다.