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

백준의 4연산(14395) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1. 맞은 사람도 별로 없고 정답률도 굉장히 낮은 문제이다. 사실 좀 어렵기도 했다.

   풀이는 생각보다 어렵지 않다.

   본인은 BFS를 이용해서 풀었는데, Queue에 (longlong, string)을 쌍으로 관리해주었다.

   이 때, int가 아닌 long long을 사용한 이유는, 중간 계산 과정에서 int형이 범위를 초과하는 값들이 발생해서 계산이

   제대로 안될 때가 있기 때문이다.

2. BFS에서는 현재의 값을 +, -, *, / 4가지 연산에 다해보고 그 연산에 대한 결과값이 이미 탐색한적 없고, 그 값이 1보다

  작지 않은 값이라면 Queue에 연산의 결과값과 연산기호를 넣어주었다.

3. 이 후, 결과값에 도달하게 되면 Queue에 저장되어 있는 string 변수에 저장되어 있는 연산기호들을 출력을 해주는데,

   여기서 한 가지 주의해야 할 점이 있다.

   문제에 보면 " 연산의 아스키 코드 순서는 '*', '+', '-', '/' 이다. " 라는 말이 있다.

   처음에는 이게 무슨 말인지 몰랐는데, 쉽게 말하자면

   시작값이 2이고 결과값이 4라고 해보자.

   이 경우 +연산을 해도, * 연산을 해도 결과값이 나오게 된다. 즉, Queue에 +가 먼저들어가냐, *가 먼저들어가냐

   구현하는 사람에 따라 다를 수 있는 부분이다. 하지만 정답은 * 라는 것이다.

   그래서 본인은, Queue에서 계산을 할 때, 순서를 * + - / 순서대로 연산을 진행하도록 하였다.

[ 소스코드 ]

#include<iostream>
#include<string>
#include<queue>
#include<set>
 
typedef long long ll;
 
#define endl "\n"
using namespace std;
 
bool Answer = false;
ll Start, End;
string Dr[] = { "*", "+", "-", "/" };
set<ll> S;
 
void Input()
{
    cin >> Start >> End;
    if (Start == End)
    {
        cout << 0 << endl;
        exit(0);
    }
}
 
ll Calculate(ll a, int Idx)
{
    if (Idx == 0) return (a * a);
    else if (Idx == 1) return (a + a);
    else if (Idx == 2) return (a - a);
    else if (Idx == 3) return (a / a);
}
 
string BFS()
{
    queue<pair<ll, string>> Q;
    Q.push(make_pair(Start, ""));
    S.insert(Start);
 
    while (Q.empty() == 0)
    {
        ll x = Q.front().first;
        string s = Q.front().second;
        Q.pop();
 
        if (x == End)
        {
            Answer = true;
            return s;
        }
        for (int i = 0; i < 4; i++)
        {
            ll nx = Calculate(x, i);
            if (nx < 1) continue;
            if (S.find(nx) != S.end()) continue;
            S.insert(nx);
            Q.push(make_pair(nx, s + Dr[i]));
        }
    }
    return "a";
}
 
void Solution()
{
    string R = BFS();
    if (Answer == true) cout << R << endl;
    else cout << "-1" << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}