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

문제 링크 : https://www.acmicpc.net/problem/14395

14395번: 4연산

이 문제는 복잡한 연산 없이 '-' 와 '/'의 사용 횟수 제한만 알고있으면 금방 풀 수 있다.

어떠한 숫자라도 '-'을 사용하면 0이되고, '/'를 사용하면 1이 된다.

때문에 '-'연산과 '/'연산을 사용하는 최대 횟수는 각 1번으로 제한을 두면 된다.

 

또한 연산 결과가 0과 1일때 발생할 수 있는 문제사항들을 if로 제거해주면 된다.

문제사항들은 다음과 같다.

 

• 1*1은 1이므로 이런 계산을 방지해야한다.
• 0+0은 0이므로 이런 계산을 방지해아한다.
• 0*0은 0이므로 이런 계산을 방지해야한다.

로직만 이해하면 디테일한 해설은 불필요하므로, 구체적인 해설은 생략한다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

struct four{
    unsigned long long num;
    string ans;
};

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int mini = 0, div = 0;
    unsigned long long s,t;
    cin >> s >> t;
    queue<four> q;
    q.push({s,""});
    while(!q.empty()){
        unsigned long long a = q.front().num;
        string temp = q.front().ans;
        q.pop();
        if(a==t){
            if(temp=="") cout << 0 << "\n";
            else cout << temp << "\n";
            exit(0);
        }
        if(a*a<=t&&a*a>1) q.push({a*a,temp+'*'}); // '*'
        if(a+a<=t&&a+a>0) q.push({a+a,temp+'+'}); // '+'
        if(mini==0){
            q.push({0,temp+'-'}); // '-'
            mini=1;
        }
        if(div==0){
            q.push({1,temp+'/'}); // '/'
            div = 1;
        }
    }
    cout << -1 << "\n";
    return 0;
}