[BOJ/백준][Gold5] 14395 : 4연산 (C++)

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

14395번: 4연산

 

[난이도] Gold5
[유형] BFS

[풀이]
*,+,-,/를 모두 사용하면서 연산을 진행하면 굉장히 많은 경우의 수가 나올 것 같지만
생각해보면 '-'는 사용할 일이 없습니다. '-' 연산을 사용하면 무조건 0이 되는데
결과값인 t이 1 이상이기 때문에 어떤 입력에도 0을 만들 일이 없습니다.
'/'의 사용시 무조건 1을 만들기 때문에 최초 1회에만 사용하는 것이 의미가 있습니다.

결국 시작 숫자 s에서 *,+를 이용해 t를 만드는 경우와, 처음에 '/' 연산을 사용해
1을 만든 뒤 *,+를 이용해 t를 만드는 경우 둘 중 최적의 경우를 찾으면 됩니다.

수의 범위가 10^9이므로 많은 수가 등장할 것 같지만 +,* 연산을 이용할 경우 수가 큰 폭으로 증가하므로
10^9에 도달할 때까지 10^9만큼 많은 수가 등장하지는 않을 것입니다.
이를 이용해 set으로 visit한 숫자에 체크를 해주는 BFS를 사용할 수 있습니다.

s부터 시작해 t를 만든 경우, '/' 연산을 사용해 1부터 시작해 t를 만든 두 경우를 비교해서
최적의 답을 구해주면 됩니다.

 

#include <cstdio>
#include <string>
#include <set>
#include <iostream>
#include <queue>
using namespace std;
using ll = long long;
ll s,t;
string sol(ll sv,string sstr){
    queue<pair<ll,string>> q;
    q.push({sv,sstr});   
    set<ll> visit;
    visit.insert(sv);
    while(!q.empty()){
        auto [v,str] = q.front();
        q.pop();
        if(v==t) return str;

        if(v*v<=t && visit.find(v*v)==visit.end()) {
            visit.insert(v*v);
            q.push({v*v,str+"*"});
        }
        if(v+v<=t && visit.find(v+v)==visit.end()) {
            visit.insert(v+v);
            q.push({v+v,str+"+"});
        }

    }     
    return "0";
}
int main(){
    cin >> s >> t;
    if(s==t) {
        cout << 0;
        return 0;
    }
    string ans1 = sol(s,"");
    string ans2 = sol(1,"/");
    if(ans1=="0" && ans2=="0") cout << -1;
    else if(ans1=="0") cout << ans2;
    else if(ans2=="0") cout << ans1;
    else {
        if(ans1.size()<ans2.size()) cout << ans1;
        else if(ans1.size()>ans2.size()) cout << ans2;
        else{
            if(ans1<ans2) cout << ans1;
            else cout << ans2;    
        }   
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/14395.cpp