4연산 14395

문제

접근 방법

BFS를 활용하여 4연산을 수행해주면 된다고 생각했다.

하지만 4연산 중 2연산은 같은 자리를 계속 지정해준다. 나누기는 계속하여 자신을 나누기에 1이 나오고 뺄셈은 계속하여 자신을 빼기에 0이 나온다. 즉 반복할 필요가 없는 요소이다.

그것을 해결하기 위해선 뺄셈은 무시하여주고 (t는 0의 값이 나올 일이 없기 때문이다) 결괏값이 1인지 확인해준 뒤 1을 큐에 같이 넣어주면 된다.

코드

#include <iostream>
#include <map>
#include <queue>
#include <string>
using namespace std;
typedef long long ll;
typedef pair<ll, string> pis;
map<ll, bool> visted;
queue<pis> q;
ll s, t;
void push(ll num, string str)
{
    if (num > t || visted[num])
        return;
    visted[num] = true;
    if (num == t)
    {
        cout << str;
        exit(0);
    }
    q.push({num, str});
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> s >> t;
    if (s == t)
    {
        cout << 0;
        return 0;
    }
    else if ((s * s) == t)
    {
        cout << "*";
        return 0;
    }
    else if ((s << 1) == t)
    {
        cout << "+";
        return 0;
    }
    else if (t == 1)
    {
        cout << "/";
        return 0;
    }
    q.push({s * s, "*"});
    q.push({s << 1, "+"});
    q.push({1, "/"});
    visted[s] = visted[s * s] = visted[s << 1] = visted[1] = true;
    while (!q.empty())
    {
        pis cur = q.front();
        q.pop();
        push(cur.first * cur.first, cur.second + "*");
        push(cur.first << 1, cur.second + "+");
    }
    cout << -1;
    return 0;
}

풀이

2가지를 실수했었다.

1. 변수형을 int로 했었다는 것
2. 초반에 s==t인 경우와 t==1인 경우만 확인한 것

t와 s의 범위가 10억 이하지만 곱하는 과정에서 10억을 초과하는 값이 나오기 쉽다. 그렇기에 long long으로 해주어야 한다.

s==t, t==1인 경우만 확인하고 바로 s와 1의 값을 큐에 담았었다. 하지만 이렇게 하면 '사전 순'을 해결해주지 못한다.
왜냐하면 *와 +가 더 빠른데 /가 더 빨리 나오는 결과를 내기 때문이다. (/,*,+순이 돼버린다)
*와 +을 큐에 먼저 집어넣어 주게끔 수정해주면 된다.

쉽게 풀 수 있지만 실수하기도 쉬운 문제인 것 같다.
또한 사칙연산의 사전 순을 몰랐던 입장에선 아스키코드를 검색할 수 없었다면 조금 지체되지 않았을까 싶다.